1. Идея

Нужно найти минимальное число шагов от стартовой клетки до ближайшей свободной клетки на границе, но стартовая клетка выходом не считается.

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

Мы запускаем BFS из стартовой клетки и постепенно рассматриваем все клетки на расстоянии 1, потом на расстоянии 2, потом на расстоянии 3 и так далее. Как только впервые попадаем в подходящую граничную клетку, это и есть ответ.

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

Наблюдение 1. Сетка — это граф

Каждую свободную клетку '.' можно считать вершиной графа.

Из клетки можно перейти в 4 соседние по стороне клетки:

• вверх
• вниз
• влево
• вправо

если они:

• не выходят за границы поля;
• не являются заваленными, то есть не равны '+'.

Наблюдение 2. Нужен именно ближайший выход

Если искать путь "в глубину", можно случайно найти не самый короткий маршрут.

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

Наблюдение 3. Старт на границе не считается выходом

По условию выходом считается любая граничная свободная клетка, кроме стартовой.

Поэтому нельзя сразу сказать, что ответ равен 0, если старт стоит на границе. Нужно именно перейти в другую граничную клетку.

В эталонном решении это учитывается очень удобно: стартовая клетка просто добавляется в очередь, а выход проверяется только для соседних клеток, в которые мы переходим.

Наблюдение 4. Посещённые клетки нужно помечать

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

В эталонном решении для пометки посещения используется сама матрица: посещённая клетка превращается в '+'. Это удобно, потому что не нужен отдельный массив used.

3. Алгоритм

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

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

Докажем, что алгоритм действительно находит минимальное расстояние до ближайшего выхода.

1. BFS рассматривает клетки по возрастанию расстояния

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

Когда мы извлекаем клетку с расстоянием dist, все её непосещённые соседи получают расстояние dist + 1 и добавляются в конец очереди.

Значит:

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

Это основное свойство BFS в невзвешенном графе.

2. Первая найденная граничная клетка даёт кратчайший путь

Как только мы нашли соседнюю свободную клетку на границе и собираемся перейти в неё за dist + 1 шагов, это означает, что существует путь длины dist + 1.

Мог ли существовать более короткий путь к какому-то выходу?

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

Следовательно, первое найденное значение и есть минимальное число шагов до ближайшего выхода.

3. Мы не пропускаем возможные пути

Из каждой достижимой свободной клетки мы перебираем все 4 возможных перехода.

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

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

4. Стартовая клетка не считается выходом

Алгоритм не проверяет старт на выход до начала BFS.

Проверка на границу выполняется только для соседних клеток, в которые делается переход. Поэтому стартовая клетка, даже если она граничная, не может быть ошибочно принята за ответ.

Итак, алгоритм корректен.

5. Сложность

Пусть всего n строк и m столбцов.

Каждая клетка:

• не более одного раза попадает в очередь;
• не более одного раза обрабатывается.

Для каждой обработанной клетки мы проверяем 4 направления.

Поэтому:

• время работы: O(n * m)
• память: O(n * m) в худшем случае из-за очереди

При ограничениях до 100 x 100 это работает очень быстро.

6. Код на C++17

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

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

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

    int sr, sc;
    cin >> sr >> sc;

    queue<array<int, 3>> q;
    q.push({sr, sc, 0});
    maze[sr][sc] = '+';

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

    while (!q.empty()) {
        auto cur = q.front();
        q.pop();

        int r = cur[0];
        int c = cur[1];
        int dist = cur[2];

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

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

            if (nr == 0 || nr == n - 1 || nc == 0 || nc == m - 1) {
                cout << dist + 1 << '\n';
                return 0;
            }

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

    cout << -1 << '\n';
    return 0;
}

7. Код на Python 3

import sys
from collections import deque

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

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

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

    sr = int(next(it))
    sc = int(next(it))

    q = deque()
    q.append((sr, sc, 0))
    maze[sr][sc] = '+'

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

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

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

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

            if nr == 0 or nr == n - 1 or nc == 0 or nc == m - 1:
                print(dist + 1)
                return

            maze[nr][nc] = '+'
            q.append((nr, nc, dist + 1))

    print(-1)

if __name__ == "__main__":
    solve()