BFS на сетке с препятствиями — задача «Лабиринт» РАЗБОР

6 мая 2026 г.CodePal-тренер

⚡ 1400
bfs
grafy
grid
shortest-path
graph-search
queue

BFS (обход в ширину) — техника, у которой два центральных свойства: за один проход от стартовой вершины она находит кратчайший путь до каждой достижимой вершины, и она умеет это в графе, где все рёбра одной стоимости. Сетка с препятствиями — это и есть такой граф: вершины — свободные клетки, рёбра — соседство по сторонам, каждое ребро имеет «вес» 1 шаг.

Эта задача — эталонный учебный кейс. Условие звучит как «лабиринт», но за словом «лабиринт» — обычная сетка из символов, и сразу понятно: каждая клетка соответствует вершине графа, каждая пара соседних свободных клеток — ребру. Дальше — BFS, очередь, расстояния по уровням. Содержательное упражнение — не сам алгоритм (он шаблонный), а аккуратная реализация: правильное чтение ввода, обработка границ, защита от повторного посещения, корректный вывод $-1$ при отсутствии пути.

Что дано

Прямоугольная сетка $n \times m$ . Каждая клетка — либо «.» (свободно), либо «#» (стена). Заданы координаты двух свободных клеток: стартовой $(r_s, c_s)$ и финишной $(r_t, c_t)$ . Игрок стартует в $(r_s, c_s)$ и может за один ход перейти на одну из четырёх соседних клеток (вверх, вниз, влево, вправо), если она существует в сетке и не является стеной.

Нужно найти минимальное число шагов, за которое игрок может добраться от старта до финиша. Если путь не существует — вывести $-1$ .

Ограничения

$1 \le n, m \le 10^3$ .
$1 \le r_s, r_t \le n$ , $1 \le c_s, c_t \le m$ .
Стартовая и финишная клетки — гарантированно свободные.
Координаты — 1-индексированные (первая строка — индекс 1).

Формат ввода

n m
<строка 1 сетки>
<строка 2 сетки>
...
<строка n сетки>
r_s c_s r_t c_t

Формат вывода

Одно целое число — минимальное число шагов или $-1$ , если пути нет.

Пример A

5 5
.....
.###.
.....
.###.
.....
1 1 5 5

Сетка нарисована в виде:

.....    (1,1) — старт
.###.
.....
.###.
.....    (5,5) — финиш

Между стартом и финишем стоят две «полки» стен в строках 2 и 4. Однако столбец 5 — свободен, как и столбец 1, поэтому путь можно проложить, например, так: «вправо до (1,5), вниз до (5,5)» — итого 4 шага вправо + 4 шага вниз = 8 шагов. Любой другой путь будет такой же длины или длиннее.

Ответ — $8$ .

Пример B

4 4
....
####
....
....
1 1 4 4

Строка 2 — сплошная стена через всю ширину, отрезающая верхнюю строку от остальных. Старт в (1,1), финиш в (4,4) — между ними не пройти.

Ответ — $-1$ .

Пример C

5 5
.....
####.
.....
.####
.....
1 1 5 1

Сетка:

.....    (1,1) — старт
####.
.....
.####
.....    (5,1) — финиш

Сразу спуск из (1,1) вниз невозможен — мешает стена. Нужно идти змейкой: правой стороной строки 1 → через свободный (2,5) вниз → влево по строке 3 → через (4,1) вниз → к финишу. Минимальный путь — 12 шагов.

Ответ — $12$ .

Идея решения

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

Состояние BFS — двумерный массив $dist[r][c]$ , инициализированный значением «не посещено» (например, $-1$ ). $dist[r_s][c_s] = 0$ . Из любой клетки $(r, c)$ с известным $dist$ мы пробуем сделать шаг в одну из 4 соседних клеток $(r', c')$ ; если $(r', c')$ в пределах сетки, свободна и ещё не посещена, ставим $dist[r'][c'] = dist[r][c] + 1$ и добавляем в очередь.

Главная гарантия алгоритма: когда BFS впервые помечает клетку $(r', c')$ , это происходит на минимальном уровне. Дальнейшие пути в эту же клетку через другие соседи не уменьшат расстояние — поэтому метку $dist$ можно ставить в момент добавления в очередь, не дожидаясь извлечения. Это сразу решает проблему повторных посещений: помеченная клетка больше в очередь не попадёт.

Руками на примере A

$n = m = 5$ , сетка как в условии, старт $(1, 1)$ , финиш $(5, 5)$ . Будем работать в 0-индексации (то есть старт $(0, 0)$ , финиш $(4, 4)$ ) — потому что массивы в коде нумеруются с нуля.

Уровни BFS — клетки на одинаковом расстоянии от старта. Покажу расстояния прямо в сетке (звёздочка * — стена; число — dist):

Уровень 0:
0 . . . .
. * * * .
. . . . .
. * * * .
. . . . .

Уровень 1 (соседи (0,0)):
0 1 . . .
1 * * * .
. . . . .
. * * * .
. . . . .

Уровень 2:
0 1 2 . .
1 * * * .
2 . . . .
. * * * .
. . . . .

Уровень 3:
0 1 2 3 .
1 * * * .
2 3 . . .
3 * * * .
. . . . .

Уровень 4:
0 1 2 3 4
1 * * * .
2 3 4 . .
3 * * * .
4 . . . .

И так далее. На уровне 8 первая распакованная клетка (4,4) получит метку $8$ :

Уровень 8:
0 1 2 3 4
1 * * * 5
2 3 4 5 6
3 * * * 7
4 5 6 7 8

Чтобы убедиться руками: пройдём от (0,0) до (4,4) по нашему правилу. Лучший путь — через свободный столбец $c=4$ или строку $r=0$ + столбец $c=0$ для зеркала. Любой такой путь даёт ровно $4 + 4 = 8$ шагов. ✓

Обратите внимание: на уровне 7 клетка $(3, 4)$ получит метку $7$ (так как соседи стенки — недостижимы напрямую, нужно идти через $(2, 4)$ ). Это и есть единственная клетка четвёртой строки, до которой расстояние конечно — все клетки $(3, 1), (3, 2), (3, 3)$ — стены.

Алгоритм

прочитать n, m, сетку, r_s, c_s, r_t, c_t (перевести в 0-индексацию)

dist[i][j] ← -1 для всех (i, j)
dist[r_s][c_s] ← 0

очередь q
поставить (r_s, c_s) в q

пока q не пуста:
    (r, c) ← извлечь из q
    для (dr, dc) из [(-1,0), (1,0), (0,-1), (0,1)]:
        nr, nc ← r + dr, c + dc
        если 0 ≤ nr < n, 0 ≤ nc < m, сетка[nr][nc] = '.', dist[nr][nc] = -1:
            dist[nr][nc] ← dist[r][c] + 1
            поставить (nr, nc) в q

вывести dist[r_t][c_t]

Сложность. Время — $O(n \cdot m)$ : каждая клетка кладётся в очередь не более одного раза и обрабатывается за $O(1)$ (четыре проверки соседей). Память — $O(n \cdot m)$ под массив dist и очередь.

Можно ли остановиться, как только достали финишную клетку? Да: как только из очереди извлечена $(r_t, c_t)$ , её dist — окончательный, дальше можно не идти. Это даёт в среднем ускорение в 2 раза (по статистике, целевая клетка достигается раньше, чем заполнена вся сетка), асимптотику не меняет. В коде ниже я не делаю раннего выхода — для простоты; добавить — три строки.

Код решения

Комментарии по реализации

Тип расстояния. В этой задаче int достаточно: $n \cdot m \le 10^6$ , любое расстояние не больше $10^6$ . В Python это всегда «большой» int.
Где ставить метку — при добавлении в очередь или при извлечении. При добавлении. Это критично. Если ставить при извлечении, одна и та же клетка может попасть в очередь несколько раз (через разных соседей), что раздувает память до $O(n \cdot m \cdot k)$ и ухудшает время. Метка при добавлении гарантирует, что каждая клетка в очереди — ровно один раз.
Ранний выход. if (r, c) == (rt, ct) break; — найдённое значение dist[rt][ct] уже минимально. Без раннего выхода работа не сломается, но сделает лишние ходы. На худшем тесте с финишем в дальнем углу выгоды нет; на средних тестах ускорение часто двукратное.
Направления обхода — массив, не четыре отдельных условия. Цикл по (dr, dc) короче и меньше шансов опечататься. На производительность не влияет.
Чтение сетки. В C++ cin >> g[i] читает строку без пробелов и без переводов строки — что нужно. В Python — через data (split по любым whitespace) каждый «токен» — отдельная строка сетки; работает, если строка не содержит пробелов внутри.
Очередь — deque в Python, queue<pair<int,int>> в C++. Производительность очереди критична для $10^6$ клеток. list.pop(0) в Python работает за $O(n)$ — нельзя; deque.popleft за $O(1)$ — нужно.
Проверка границ. Сначала границы, потом всё остальное. Обратный порядок (сначала g[nr][nc] != '.', потом границы) — out-of-bounds на краях сетки, что в C++ — UB.

Проверка на примерах

Пример A — $8$ шагов

Старт $(0, 0)$ , финиш $(4, 4)$ . BFS-уровни выше показали, что $(4, 4)$ помечается на уровне 8. Один из путей длины $8$ :

(0,0) \to (0,1) \to (0,2) \to (0,3) \to (0,4) \to (1,4) \to (2,4) \to (3,4) \to (4,4).

Любой более короткий путь невозможен: даже без стен расстояние $|r_s - r_t| + |c_s - c_t| = 4 + 4 = 8$ — это нижняя оценка по Манхэттенской метрике. Стены не «удлинили» путь, потому что свободный столбец 4 позволил пройти эту нижнюю оценку. ✓

Пример B — $-1$

Строка 2 — #### — отделяет $(0, 0)$ от всей остальной сетки. BFS из $(0, 0)$ заполнит только строку 0; $(3, 3)$ останется с $dist = -1$ . ✓

Пример C — $12$ шагов

Один из путей:

(0,0) \to (0,1) \to (0,2) \to (0,3) \to (0,4) \to (1,4) \to (2,4) \to (2,3) \to (2,2) \to (2,1) \to (2,0) \to (3,0) \to (4,0).

Длина — $12$ . Манхэттенская оценка $|0 - 4| + |0 - 0| = 4$ , фактическое расстояние — $12$ : стены вынудили обход через столбец 4. ✓

Крайние случаи

Старт равен финишу. $dist[r_s][c_s] = 0$ ставится до цикла; в первой же итерации проверка (r, c) == (rt, ct) истинна, ответ $0$ — без ошибок.
Стартовая клетка — стена. Условие гарантирует, что старт свободен; защитная проверка g[rs][cs] != '.' не нужна. Но в более общей задаче (например, старт не гарантирован свободным) её стоит добавить — иначе BFS будет распространяться из «стены», что некорректно.
Финиш — стена. По условию гарантировано не бывает. Если на ослабленных входах возникнет — BFS никогда не пометит её (стены отфильтрованы при переходе), и dist[rt][ct] останется $-1$ , что даст правильный «нет пути».
Полностью заполненная стенами сетка. Все клетки кроме старта — стены. BFS обработает только старт, очередь опустеет на втором шаге. Ответ для любого финиша $\neq$ старт — $-1$ .
Сетка $1 \times 1$ . Старт = финиш = $(0, 0)$ . Ответ — $0$ .
Сетка $n \times 1$ или $1 \times m$ . Вырожденный случай: «1D-лабиринт». BFS работает без модификаций; если на пути нет стены — ответ $|r_s - r_t|$ или $|c_s - c_t|$ .

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

Метка visited при извлечении, а не при добавлении. Самая массовая ошибка: программа работает корректно, но на больших тестах падает по памяти или TL — каждая клетка добавляется в очередь $O(1)$ раз только при правильной семантике. При метке «при извлечении» одна клетка может оказаться в очереди до 4 раз, что раздувает память в 4 раза и время — пропорционально.
Восемь направлений вместо четырёх. Условие задаёт 4-связность (только по сторонам). Если случайно добавить диагональные смещения $(\pm 1, \pm 1)$ , ответ будет занижен — диагональный шаг «по правде» стоит $\sqrt{2}$ , а здесь BFS считает его за $1$ , что в задаче с 4-связностью неверно.
0-индексация / 1-индексация. В условии координаты обычно 1-индексированные, в коде массивы — 0-индексированные. Забыть --rs; --cs; (или rs - 1) — частая ошибка, дающая «правильное число на тривиальных примерах, но WA на пограничных случаях» (например, старт на краю сетки).
Проверка границ после доступа к ячейке. Запись g[nr][nc] == '.' && nr >= 0 — UB на границах сетки. Проверка границ должна предшествовать любому обращению к g[nr][nc]. В Python это даст IndexError (заметно сразу), в C++ — undefined behavior (программа может работать «правильно» и упасть на CF-сервере).
list.pop(0) вместо deque.popleft в Python. Список — это динамический массив; удаление из начала — $O(n)$ . На сетке $10^3 \times 10^3$ это даёт $\sim 10^{12}$ операций — гарантированный TL. deque решает это за $O(1)$ .
Игнорирование случая «финиш недостижим». Если просто вывести dist[rt][ct], не обработав случай $-1$ , в задачах с другим форматом «нет пути» (например, вывести «IMPOSSIBLE») будет неправильный формат вывода. Здесь сам $-1$ устраивает по условию — но привычка явно обрабатывать недостижимость полезна.
Использование DFS вместо BFS. DFS на невзвешенном графе не гарантирует кратчайший путь. Программа может «дойти до финиша», но через длинный окольный путь и вернуть неоптимальный ответ. Если задача про минимум шагов — обязательно BFS.
Обход по символам строки в Python через for ch in grid[r]. Аккуратно, если переходим к редким оптимизациям: при обходе клеток в порядке 1D — можно потерять координаты. На обычной BFS-задаче не критично.

Сложность

Время. $O(n \cdot m)$ . Каждая клетка кладётся в очередь не более одного раза и обрабатывается за $O(1)$ . На $n = m = 10^3$ — $\sim 10^6$ операций, около 0.2 сек в C++, 1–2 сек в Python.
Память. $O(n \cdot m)$ под массив расстояний и сетку. На $10^3 \times 10^3$ — $\sim 4$ МБ в C++ (int), в Python $\sim 30$ МБ (list of list of int).
Очередь. Размер очереди ограничен числом свободных клеток, в худшем случае — $n \cdot m$ . Дополнительной памяти — $O(n \cdot m)$ .

Линейная сложность по числу клеток — теоретический минимум для задачи: даже просто прочитать сетку требует $O(n \cdot m)$ операций.

Связанные задачи

BFS с несколькими стартами. Если стартов несколько ( $k$ клеток), кладём все $k$ в очередь сразу с расстоянием $0$ . Тогда dist[i][j] — расстояние до ближайшего старта. Это популярная модификация (пожар в сетке, заражение, разлив воды).
BFS на расширенном состоянии. Когда у игрока есть параметры состояния — топливо, ключи, направление взгляда — состояние BFS превращается в кортеж $(r, c, \text{state})$ , очередь и dist индексируются всеми компонентами. Эта тема — отдельная статья на полосе 1700–1900.
0–1 BFS. Если рёбра бывают двух весов — $0$ и $1$ — обычный BFS перестаёт работать. Замена — deque-based 0–1 BFS: рёбра весом $0$ добавляются в начало очереди, весом $1$ — в конец. Сложность та же $O(V + E)$ . Полоса 1800–2000.
Дейкстра на сетке. Если рёбра — разной (произвольной положительной) стоимости — BFS уже не подходит, нужна Дейкстра за $O((V + E) \log V)$ . Сетка $n \times m$ — это $V = O(n m)$ , $E = O(n m)$ , итого $O(n m \log (n m))$ .
BFS + восстановление пути. Если задача требует не только длину, но и сам путь — хранить дополнительно parent[r][c] = (pr, pc) (откуда мы пришли), потом восстанавливать обратным проходом от финиша к старту. Память — те же $O(n \cdot m)$ .

Итого

Идея: BFS из стартовой клетки строит расстояния по уровням. Первый раз, когда финишная клетка попадает в очередь, — это минимальное расстояние.
Ключевая оптимизация: ставить dist[r][c] в момент добавления в очередь — иначе клетка может попасть в очередь несколько раз.
Структура: массив dist[n][m] + очередь deque/queue. 4 направления. Проверка границ перед обращением к ячейке.
Сложность: $O(n \cdot m)$ времени и памяти.
Главные ловушки: метка при добавлении (не извлечении), 4 vs 8 направлений, 0/1-индексация, deque вместо list.pop(0) в Python, проверка границ перед доступом.
Когда BFS НЕ подходит: рёбра разной стоимости (Дейкстра / 0–1 BFS), требуется не минимум, а число путей (DP), большие $n \cdot m$ с состоянием (BFS на расширенном состоянии).

Источник задачи: классический BFS-лабиринт жанра задач acmp.ru.

Попробуй разобрать похожие задачи

В CodePal AI-партнёр подсказывает идею, а не ответ. Разбор в диалоге, код проверяется в браузере.