Кратчайший путь в сетке
Дан лабиринт, представленный в виде сетки из r строк и c столбцов. Вам необходимо определить длину кратчайшего пути от стартовой клетки до конечной.
Лабиринт обозначен так:
Проходимые клетки указаны точками (
.).Стены обозначены символами решётки (
#).Стартовая точка помечена заглавной буквой
S.Конечная клетка помечена заглавной буквой
E.
Вы можете перемещаться по соседним клеткам (влево, вправо, вверх или вниз), если там нет стены.
Требуется вычислить длину кратчайшего пути между клеткой S и клеткой E.
Входные данные
Первая строка содержит два целых числа r и c (1 ≤ r, c ≤ 1000).
Следующие r строк содержат по c символов, описывающих сетку. Каждая клетка может быть либо проходной (.), либо стеной (#), либо стартовой (S), либо конечной (E). Гарантируется, что во всей сетке существует ровно одна клетка S и ровно одна клетка E.
Выходные данные
Программа должна вывести длину кратчайшего пути от S до E. Если пути от S до E не существует, выведите Impossible.
Примеры
Input
5 8
########
##.S....
....#.#.
#......#
...#...EOutput
7Подсказка
Не всегда обязательно явно строить граф, чтобы запустить алгоритм BFS (поиск в ширину). Иногда достаточно использовать неявное представление графа, например сетку, и всё равно выполнять на ней поиск в ширину.
Намёк
Можно считать сетку графом и хранить двумерный массив расстояний d[][], который отражает кратчайшее расстояние от стартовой клетки до текущей.
Constraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB