Короткая тропа в лабиринте

Юный искатель приключений попал в древний лабиринт. В одной клетке он стартует (S), в другой лежит артефакт (T). За один ход можно перейти в соседнюю по стороне клетку (вверх/вниз/влево/вправо), но стены (#) непроходимы.

Нужно узнать, за сколько ходов можно добраться до артефакта кратчайшим путём. Если пути нет — сообщить об этом.

Формат ввода

• В первой строке два целых числа m и n — размеры лабиринта.
• Далее идут m строк по n символов в каждой — карта лабиринта.
• S — старт (ровно один раз)
• T — цель (ровно один раз)
• . — свободная клетка
• # — стена

Формат вывода Выведите одно целое число — минимальное число ходов от S до T. Если добраться нельзя, выведите -1.

Ограничения

• 2 ≤ m ≤ 80, 2 ≤ n ≤ 80
• Разрешены только символы S, T, ., #

Пример Ввод:

4 5
S..#.
##.#.
...#.
.#..T

Вывод:

7

Ключевое наблюдение: каждый ход в соседнюю клетку стоит одинаково (1). Значит, лабиринт можно представить как граф, где вершины — клетки, а рёбра — переходы вверх/вниз/влево/вправо. В таком графе кратчайшие расстояния от старта до всех клеток надёжно находит BFS (поиск в ширину): он расширяет «фронт» слоями по расстоянию 0, 1, 2…

Почему BFS работает: очередь гарантирует, что мы обрабатываем клетки в порядке неубывающего расстояния, поэтому как только до клетки дошли впервые, это уже минимальное число шагов.

План решения:

• Считать m, n, затем карту.
• Найти координаты S и T.
• Завести массив dist[m][n] (например, заполнить большим числом) или visited.
• Положить S в очередь, поставить dist[S] = 0.
• Пока очередь не пуста:
• достать клетку (x, y);
• перебрать 4 направления (dx, dy);
• для соседа (nx, ny) проверить границы и что это не #;
• если он ещё не посещён, задать dist[nx][ny] = dist[x][y] + 1 и добавить в очередь.
• Ответ: если dist[T] не обновился — вывести -1, иначе dist[T].

Мини-сниппет перехода: dist[nx][ny] = dist[x][y] + 1.

Сложность: каждая клетка попадает в очередь максимум один раз, поэтому время O(m*n), память O(m*n).

Частая ошибка: пытаться решать DFS (поиск в глубину) — он не гарантирует кратчайший путь; или отмечать клетку посещённой слишком поздно, из-за чего она добавляется в очередь много раз.