Кратчайший путь с ключами и дверями

Дана сетка grid из строк одинаковой длины: '.' - свободная клетка, '#' - стена, '@' - старт, строчная буква 'a'-'f' - ключ, заглавная 'A'-'F' - дверь, которую можно пройти только уже имея соответствующий ключ. Верните минимальное число шагов, чтобы собрать ВСЕ ключи, присутствующие на карте. Если это невозможно, верните -1. Состояние поиска - не просто клетка, а пара (клетка, набор собранных ключей как битовая маска) - BFS по расширенному пространству состояний.