Кратчайший путь в сетке
Дан лабиринт, представленный в виде сетки из
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