1. Идея

Нужно найти минимальное число шагов от клетки (1, 1) до клетки (n, m) в прямоугольной сетке, где можно ходить только по свободным клеткам . и только в 4 направлениях.

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

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

Мы будем рассматривать каждую клетку как вершину графа:

• из клетки можно перейти в соседние по стороне клетки;
• переход возможен только если клетка находится внутри поля и не является препятствием #.

BFS гарантирует, что первая найденная длина пути до клетки будет минимальной.

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

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

Хотя в условии дан лабиринт в виде таблицы, его удобно воспринимать как граф:

• каждая свободная клетка — вершина;
• между двумя соседними свободными клетками есть ребро.

Тогда задача — найти кратчайший путь из стартовой вершины в конечную.

Наблюдение 2. Все рёбра одинаковые

За один ход робот перемещается в соседнюю клетку. Значит, вес каждого перехода одинаков и равен 1.

Это важное свойство: если все рёбра равны, не нужен Дейкстра — достаточно BFS.

Наблюдение 3. Нужно хранить расстояния

Чтобы не заходить в одну и ту же клетку много раз, будем хранить массив dist, где:

• dist[i][j] = -1, если клетка ещё не посещена;
• иначе dist[i][j] — минимальное число шагов от старта до этой клетки.

Начальная клетка имеет расстояние 0.

Наблюдение 4. Если цель недостижима, ответ будет -1

Если после BFS клетка (n - 1, m - 1) осталась непосещённой, значит добраться до неё нельзя.

3. Алгоритм

1. Считываем n и m.
2. Считываем карту grid.
3. Создаём двумерный массив dist размера n x m, заполняем значением -1.
4. Создаём очередь для BFS.
5. Кладём стартовую клетку (0, 0) в очередь и записываем dist[0][0] = 0.
6. Пока очередь не пуста:
   • достаём из неё текущую клетку (x, y);
   • перебираем 4 направления: вверх, вниз, влево, вправо;
   • получаем соседнюю клетку (nx, ny);
   • если она вне границ, пропускаем;
   • если там препятствие #, пропускаем;
   • если она уже посещена, пропускаем;
   • иначе записываем dist[nx][ny] = dist[x][y] + 1 и добавляем её в очередь.
7. После завершения BFS выводим dist[n - 1][m - 1].

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

BFS обходит граф слоями:

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

Это означает, что когда мы впервые попадаем в некоторую клетку, мы уже нашли кратчайший путь до неё.

Почему так?

• В очередь сначала попадает старт.
• Из него мы добавляем все клетки, до которых можно дойти за 1 шаг.
• Затем обрабатываем их и добавляем клетки на расстоянии 2.
• Очередь работает в порядке поступления, поэтому более короткие пути всегда рассматриваются раньше более длинных.

Следовательно:

• значение dist[x][y], которое мы записали при первом посещении клетки, является минимальным;
• когда BFS закончится, dist[n - 1][m - 1] будет длиной кратчайшего пути до финиша;
• если финиш недостижим, его расстояние так и останется -1.

Значит, алгоритм всегда выдаёт правильный ответ.

5. Сложность

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

Каждую клетку мы посещаем не более одного раза. Для каждой посещённой клетки проверяем 4 соседей.

Поэтому:

• время работы: O(n * m);
• память: O(n * m).

Это подходит для ограничений до 1000 x 1000.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

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

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

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        int x = cur.first;
        int y = cur.second;

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }
            if (grid[nx][ny] == '#') {
                continue;
            }
            if (dist[nx][ny] != -1) {
                continue;
            }

            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }

    cout << dist[n - 1][m - 1] << '\n';
    return 0;
}

7. Код на Python 3

from collections import deque

n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]

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

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while q:
    x, y = q.popleft()

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if grid[nx][ny] == '#':
            continue
        if dist[nx][ny] != -1:
            continue

        dist[nx][ny] = dist[x][y] + 1
        q.append((nx, ny))

print(dist[n - 1][m - 1])