plan — списке строк одинаковой длины. Каждая клетка — это один символ:
- '.' — свободный проход;
- '#' — стена;
- '@' — стартовая клетка робота (она тоже свободна);
- строчная латинская буква — ключ;
- заглавная латинская буква — дверь, которую открывает ключ с той же буквой в нижнем регистре.
За один шаг робот перемещается на соседнюю клетку вверх, вниз, влево или вправо. Выходить за пределы плана и заходить в стены нельзя. Встав на клетку с ключом, робот забирает его; пройти через дверь можно, только если её ключ уже у робота. Если на плане k ключей, то это ровно первые k букв алфавита, каждая по одному разу. Дверей с одной и той же буквой может быть несколько, а дверь, ключа от которой на плане нет, не открывается никогда.
Верните наименьшее число шагов, за которое робот соберёт все ключи. Открывать все двери не обязательно. Если собрать все ключи невозможно, верните -1.plan=['@.a', '##A', 'b..'] → 6
Сначала берём ключ a (2 шага), затем проходим дверь A под ним, спускаемся ещё на клетку и идём 2 шага влево к ключу b: всего 6 шагов.
plan=['@#a', '.#.', '...'] → 6
Стена посередине заставляет обойти её снизу: 6 шагов до ключа.
plan=['@Bb', '#Aa'] → -1
Обе двери перекрывают выход от старта, а ключи лежат за ними — собрать их нельзя, ответ -1.
len(plan) ≤ 60, 1 ≤ len(plan[i]) ≤ 60, все строки одной длиныplan[i][j] — латинская буква, '.', '#' или '@''@' встречается ровно один разplan=['@.a', '##A', 'b..']
6
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 29 тестов на сервере, включая скрытые.