1. Идея

Нужно найти ближайший выход из лабиринта от заданной стартовой клетки.

Лабиринт состоит из:

• '.' — свободная клетка,
• '+' — стена.

Разрешено ходить вверх, вниз, влево и вправо по свободным клеткам.

Выход — это любая свободная клетка на границе лабиринта, кроме самой стартовой клетки, даже если старт находится на границе.

Так как все переходы между соседними клетками имеют одинаковую стоимость 1, задача сводится к поиску кратчайшего пути в невзвешенном графе. Для этого идеально подходит поиск в ширину (BFS).

2. Наблюдения

2.1. Почему именно BFS

Если рассматривать каждую свободную клетку как вершину графа, а переход между соседними свободными клетками как ребро, то нужно найти минимальное число шагов от старта до любой подходящей граничной клетки.

BFS обходит вершины по слоям:

• сначала все клетки на расстоянии 1,
• потом все на расстоянии 2,
• затем на расстоянии 3,
• и так далее.

Значит, как только во время BFS впервые встретился выход, расстояние до него уже минимально.

2.2. Что считается выходом

Клетка является выходом, если:

1. она свободная;
2. находится на границе:
   • row == 0,
   • row == n - 1,
   • col == 0,
   • col == m - 1;
3. это не стартовая клетка.

Это важный момент: если старт расположен на краю, он не считается выходом.

2.3. Чтобы не ходить по кругу

Если не отмечать посещённые клетки, можно много раз попадать в одни и те же места и даже зациклиться.

Поэтому каждую клетку нужно посещать не более одного раза:

• либо отдельным массивом visited,
• либо изменяя сам лабиринт и превращая посещённую свободную клетку в стену.

Оба подхода корректны. Удобно использовать visited.

3. Алгоритм

Пусть размеры лабиринта n x m, вход находится в клетке (sr, sc).

1. Создаём очередь для BFS.
2. Добавляем стартовую клетку в очередь с расстоянием 0.
3. Отмечаем её как посещённую.
4. Пока очередь не пуста:
   • извлекаем текущую клетку (r, c) и расстояние d;
   • перебираем 4 соседей;
   • для каждого соседа проверяем:
     • не вышли ли за границы;
     • не стена ли это;
     • не посещали ли её раньше;
   • если сосед подходит:
     • если он является выходом, сразу возвращаем d + 1;
     • иначе помечаем его посещённым и кладём в очередь с расстоянием d + 1.
5. Если BFS завершился и выход не найден, возвращаем -1.

4. Почему это работает

Докажем корректность алгоритма.

4.1. BFS действительно рассматривает пути в порядке возрастания длины

В начале в очереди находится только стартовая клетка с расстоянием 0.

Когда из очереди извлекается клетка с расстоянием d, все новые клетки, которые можно из неё достичь за один ход, добавляются с расстоянием d + 1.

Из-за устройства очереди:

• сначала обрабатываются все клетки на расстоянии 0,
• потом все клетки на расстоянии 1,
• затем все клетки на расстоянии 2,
• и так далее.

Значит, первая обработка клетки происходит по кратчайшему пути до неё.

4.2. Первый найденный выход — ближайший

Алгоритм завершает работу в тот момент, когда впервые находит клетку-выход.

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

Следовательно, возвращаемое число шагов минимально.

4.3. Алгоритм не пропускает возможный ответ

Из стартовой клетки BFS проходит по всем достижимым свободным клеткам, причём каждую посещает не более одного раза.

Если существует путь к какому-то выходу, BFS обязательно дойдёт до него. Если BFS не нашёл ни одного выхода, значит ни один выход недостижим.

Следовательно, в этом случае ответ действительно -1.

5. Сложность

Пусть n — число строк, m — число столбцов.

• Время: O(n * m)
  Каждая клетка добавляется в очередь не более одного раза, для каждой проверяется до 4 соседей.

• Память: O(n * m)
  На массив посещений и очередь в худшем случае.

CPP

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = (int)maze.size();
        int n = (int)maze[0].size();

        vector<vector<int>> dist(m, vector<int>(n, -1));
        queue<pair<int, int>> q;

        int sr = entrance[0];
        int sc = entrance[1];

        q.push({sr, sc});
        dist[sr][sc] = 0;

        const int dr[4] = {-1, 1, 0, 0};
        const int dc[4] = {0, 0, -1, 1};

        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();

            if (!(r == sr && c == sc)) {
                if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                    return dist[r][c];
                }
            }

            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];

                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (maze[nr][nc] == '+') continue;
                if (dist[nr][nc] != -1) continue;

                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }

        return -1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;

    vector<vector<char>> maze(m, vector<char>(n));
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < n; ++j) {
            maze[i][j] = s[j];
        }
    }

    vector<int> entrance(2);
    cin >> entrance[0] >> entrance[1];

    Solution sol;
    cout << sol.nearestExit(maze, entrance) << '\n';

    return 0;
}

PYTHON

from collections import deque
import sys


class Solution:
    def nearestExit(self, maze, entrance):
        m = len(maze)
        n = len(maze[0])

        sr, sc = entrance
        dist = [[-1] * n for _ in range(m)]
        q = deque()

        q.append((sr, sc))
        dist[sr][sc] = 0

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while q:
            r, c = q.popleft()

            if not (r == sr and c == sc):
                if r == 0 or r == m - 1 or c == 0 or c == n - 1:
                    return dist[r][c]

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue
                if maze[nr][nc] == '+':
                    continue
                if dist[nr][nc] != -1:
                    continue

                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))

        return -1


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    m = int(next(it))
    n = int(next(it))

    maze = []
    for _ in range(m):
        row = list(next(it))
        maze.append(row)

    entrance = [int(next(it)), int(next(it))]

    sol = Solution()
    print(sol.nearestExit(maze, entrance))


if __name__ == "__main__":
    main()