Разбор задачи «Навигация беспилотника в городской сетке»

Идея задачи

Нам дана прямоугольная сетка N × M, в которой:

• A — стартовая клетка;
• B — целевая клетка;
• # — препятствие;
• . — свободная клетка.

За один ход можно перейти только в одну из четырёх соседних клеток:

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

Нужно найти минимальное количество шагов от A до B, либо вывести -1, если путь не существует.

Что здесь требуется заметить

Все переходы между соседними клетками имеют одинаковую стоимость: каждый ход стоит ровно 1.

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

Сетку можно воспринимать как граф:

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

Тогда задача сводится к поиску кратчайшего пути в невзвешенном графе.

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

Поиск в ширину работает слоями:

1. Сначала рассматриваются клетки на расстоянии 0 от старта.
2. Потом — все клетки на расстоянии 1.
3. Потом — на расстоянии 2.
4. И так далее.

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

Именно поэтому BFS идеально подходит для этой задачи.

Как будем хранить данные

1. Сама карта

Храним сетку как массив строк g.

2. Координаты старта и финиша

Во время чтения или отдельным проходом находим:

• (sx, sy) — координаты A;
• (tx, ty) — координаты B.

3. Массив расстояний

Создаём двумерный массив dist, где:

• dist[x][y] = -1, если клетка ещё не посещена;
• иначе dist[x][y] — минимальное число шагов от A до (x, y).

4. Очередь

Для BFS нужна обычная очередь.

Пошаговый алгоритм

1. Считываем n, m и карту.
2. Находим клетки A и B.
3. Заполняем массив dist значением -1.
4. Кладём стартовую клетку в очередь и задаём dist[sx][sy] = 0.

5. Пока очередь не пуста:

   • извлекаем текущую клетку;
   • пробуем перейти в 4 соседние клетки;

   • если сосед:

     • находится внутри границ,
     • не является препятствием,
     • ещё не посещён, то записываем для него расстояние на 1 больше и добавляем в очередь.
6. После завершения BFS ответом будет dist[tx][ty].

Если путь не найден, там так и останется -1.

Разбор на примере

Пусть есть такая сетка:

A..
.#.
..B

Стартуем из A.

• Сначала расстояние 0 имеет только A.
• Затем расстояние 1 получают соседние доступные клетки.
• Затем расстояние 2 — клетки, достижимые за два хода.
• И так далее, пока не будет достигнута B.

Так как BFS идёт по слоям, первая найденная дистанция до B и будет минимальной.

Корректность решения

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

Утверждение

Когда клетка впервые извлекается или впервые помечается в BFS, значение dist для неё равно длине кратчайшего пути от A.

Почему это верно

BFS посещает клетки в порядке неубывания расстояния от старта.

• Сначала обрабатываются все клетки на расстоянии 0.
• Затем все клетки на расстоянии 1.
• Затем на расстоянии 2.
• И так далее.

Если мы впервые пришли в клетку (x, y) из клетки (px, py), то:

dist[x][y] = dist[px][py] + 1

Причём на момент этого перехода меньшего расстояния до (x, y) уже существовать не может, иначе эта клетка была бы посещена раньше, на одном из предыдущих слоёв BFS.

Следовательно, первое найденное расстояние до любой клетки является кратчайшим.

Значит, после завершения алгоритма значение dist[tx][ty] равно минимальному числу шагов от A до B, а если клетка B недостижима, то значение останется -1.

Оценка сложности

Время

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

Итого:

O(N · M)

Память

Храним:

• саму сетку;
• массив расстояний;
• очередь.

Это тоже требует

O(N · M)

Типичные ошибки

1. Использовать DFS вместо BFS

DFS умеет находить путь, но не гарантирует минимальное количество шагов в невзвешенном графе.

2. Не отмечать посещённые клетки

Тогда одна и та же клетка может много раз попадать в очередь, что ломает эффективность.

3. Забыть проверить границы

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

4. Заходить в #

Препятствия должны полностью игнорироваться.

5. Неправильно инициализировать dist

Очень удобно заполнять его числом -1, чтобы одновременно хранить и расстояние, и факт посещения.

Решение на C++

#include <bits/stdc++.h>
using namespace std;

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

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

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

    int sx = -1, sy = -1;
    int tx = -1, ty = -1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'A') {
                sx = i;
                sy = j;
            }
            if (g[i][j] == 'B') {
                tx = i;
                ty = j;
            }
        }
    }

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

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

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

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

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

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }

            if (g[nx][ny] == '#') {
                continue;
            }

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

    cout << dist[tx][ty] << '\n';
    return 0;
}

Пояснение к коду на C++

• dist[sx][sy] = 0 — стартовая клетка находится от самой себя на расстоянии 0.
• Очередь хранит клетки, которые нужно обработать.
• Массивы dx и dy задают 4 направления движения.
• Если соседняя клетка ещё не посещалась, мы записываем её расстояние и кладём в очередь.
• В конце печатаем расстояние до B.

Решение на Python

from collections import deque

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

sx = sy = tx = ty = -1
for i in range(n):
    for j in range(m):
        if grid[i][j] == 'A':
            sx, sy = i, j
        if grid[i][j] == 'B':
            tx, ty = i, j

# dist[x][y] = минимальное расстояние от A до клетки (x, y)
dist = [[-1] * m for _ in range(n)]
q = deque()

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

# 4 направления
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 0 <= nx < n and 0 <= ny < m:
            if grid[nx][ny] != '#' and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))

print(dist[tx][ty])

Пояснение к коду на Python

В Python решение полностью повторяет ту же идею:

• deque используется как очередь;
• dist хранит расстояния и одновременно отмечает посещённые клетки;
• из каждой клетки проверяются 4 соседа;
• если до B можно добраться, в dist[tx][ty] окажется длина кратчайшего пути.