Обмен местами роботов
Вы работаете над стартапом, который стремится составить конкуренцию Boston Dynamics. Одна из задач — заставить двух роботов поменяться местами на сетке так, чтобы они не входили в одну и ту же клетку одновременно.
Сетка имеет высоту
h и ширину w, при этом пол обозначен точками (.), а стены — символами (#).Роботам разрешено ходить по соседним позициям горизонтально, вертикально и по диагонали, но они не могут находиться в одной клетке друг с другом или заходить на клетки со стенами. За один шаг каждый робот либо делает ход, либо остается на месте. При этом роботы не могут «перепрыгивать» друг через друга в одном ходе.
Требуется определить минимальное количество шагов, за которое первый робот окажется на месте второго, а второй — на месте первого.
Входные данные
В первой строке записаны два целых числа
h и w (1 ≤ h, w ≤ 50).В следующих
h строках содержится по w символов, описывающих сетку.Первый робот обозначен буквой
A, а второй робот — буквой B.Выходные данные
Выведите минимальное число шагов, за которое можно обменять роботов местами, или выведите
Impossible, если сделать это невозможно.Примеры
Ввод
4 4
AB.#
###.
...#
.###Вывод
11Ввод
2 2
AB
..Вывод
2Ввод
1 3
A.BВывод
ImpossibleConstraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB