Стратегия победы: графы — от BFS к многоходовым обходам СТРАТЕГИЯ

О чём эта статья

«Стратегия победы» — серия про траекторию тренировки, а не про одну задачу. Берём одну технику и разбираем, как она растёт от базового шаблона до полноценного применения в составных задачах.

Графы и BFS — отличный материал. На полосе CF 1300 решается одношаговый «обход в ширину из одной вершины». На 1700 — задачи требуют запускать BFS из множества источников одновременно: одна и та же модель работы с очередью, но другая инициализация. На 2100+ — состояние BFS перестаёт быть «номером вершины» и становится парой «вершина + дополнительный параметр» (маска посещённых ключей, чётность числа шагов, остаток по модулю и т. п.). Каркас «очередь + посещённость + раскраска уровней» во всех трёх случаях один и тот же; растёт размерность состояния.

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

---

Ядро техники

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

Главное свойство — корректное вычисление расстояний в невзвешенном графе (все рёбра имеют равный вес 1). Если попробовать подменить очередь на стек, мы получим DFS, который посещает все вершины, но не считает расстояния правильно. Поэтому BFS — обязательный инструмент для задач «найти кратчайший путь / минимальное число шагов / минимальное время» в невзвешенных моделях.

Базовый шаблон (псевдокод)

функция BFS(start):
    dist[v] ← +∞ для всех v
    dist[start] ← 0
    queue ← очередь, в конце которой start

    пока queue не пуста:
        v ← извлечь из головы queue
        для каждой соседней вершины u вершины v:
            если dist[u] = +∞:
                dist[u] ← dist[v] + 1
                добавить u в хвост queue

    вернуть dist

Сложность шаблона: $O(n + m)$, где $n$ — число вершин, $m$ — число рёбер. Каждая вершина добавляется в очередь и извлекается из неё ровно один раз; каждое ребро рассматривается из обоих концов (для неориентированного графа) или из одного (для ориентированного).

Что мы будем усложнять по мере роста

• Ступень 1 → ступень 2. Стартовая вершина становится множеством стартовых вершин. В очередь сразу заталкиваются все источники с dist = 0. Каркас не меняется, меняется только инициализация.
• Ступень 2 → ступень 3. Состояние перестаёт быть «номером вершины» и становится парой $(v, \text{параметр})$ — например, $(v, \text{маска собранных предметов})$ или $(v, \text{чётность пройденных шагов})$. Граф состояний разрастается до $O(n \cdot 2^k)$ или $O(n \cdot k)$, BFS работает в нём так же, только перебор соседних вершин усложняется.

Это и есть смысл серии: не «3 разные задачи», а осознанный путь между ними с явной логикой усложнения.

---

Ступень 1 — CF ~1300 (базовый шаблон)

Условие: «Кратчайший путь в невзвешенном графе»

Дан неориентированный граф с $n$ вершинами и $m$ рёбрами. Дано две вершины — старт $s$ и финиш $t$. Нужно найти длину кратчайшего пути от $s$ до $t$ (в количестве рёбер) или вывести $-1$, если пути нет.

Ограничения: $1 \le n, m \le 2 \cdot 10^5$, граф без петель и кратных рёбер.

Пример. $n = 6$, $m = 6$, рёбра $1{-}2, 2{-}3, 3{-}4, 4{-}5, 1{-}5, 5{-}6$. Старт — $1$, финиш — $4$. Ответ — $3$ (путь $1 \to 5 \to 4$ длины 2... подождите, проверим: $1 \to 5$ — ребро, $5 \to 4$ — ребро. Длина пути в рёбрах — 2). Альтернатива $1 \to 2 \to 3 \to 4$ длины 3. Минимум — 2.

Как применяется базовый шаблон

Запускаем BFS из $s$. На каждом шаге очередь даёт нам очередную вершину текущего «уровня» — вершину, до которой минимальное расстояние от $s$ уже посчитано. Все её ещё-не-посещённые соседние вершины принадлежат следующему уровню.

Когда $t$ извлекается из очереди — dist[t] содержит ответ. Если очередь опустеет, а $t$ так и не была посещена — пути нет, ответ $-1$.

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

Граф из примера, BFS из вершины 1:

Код решения

Сложность: $O(n + m)$ времени и памяти.

Что закрыли

На этом уровне мы освоили каркас BFS: очередь, массив посещённости (и одновременно расстояний), правило «новая вершина — dist + 1». На следующем шаге каркас остаётся тем же, но стартует BFS не из одной вершины, а из множества.

---

Ступень 2 — CF ~1700 (multi-source BFS)

Условие: «Расстояние до ближайшего источника на сетке»

Дана прямоугольная сетка размера $R \times C$. Каждая клетка либо проходима (символ .), либо непроходимое препятствие (символ #), либо отмечена как источник (символ *). Источников может быть несколько (от 1 до $R \cdot C$).

Для каждой проходимой клетки нужно вывести минимальное расстояние (число шагов в любом из 4 кардинальных направлений) до ближайшего источника. Если клетка непроходима — вывести -1. Если проходимая клетка не достижима ни до одного источника — вывести -1.

Ограничения: $1 \le R, C \le 10^3$, число источников до $R \cdot C$.

Пример. Сетка $3 \times 4$:

. . * .
. # . .
* . . .

Ответ:

2 1 0 1
1 -1 1 2
0 1 2 3

(Проверка: левая нижняя — это источник, расстояние 0. Соседняя сверху — расстояние 1. И так далее.)

Что меняется в шаблоне

• Состояние: клетка $(r, c)$ — то же самое, что вершина графа.
• Инициализация: в очередь сразу попадают все источники с dist = 0. Не одна вершина, а сразу множество.
• Все остальные шаги — без изменений. BFS-волна расходится одновременно из всех источников, и каждая клетка получает расстояние от ближайшего из них автоматически.

Почему это работает: BFS гарантирует, что на момент извлечения вершины $v$ из очереди значение dist[v] минимально возможное. Если в очередь сразу заложены все источники с dist = 0, то «волна» от них растекается синхронно. Любая клетка будет посещена через минимальное число шагов от ближайшего источника — никакой более далёкий источник не успеет «опередить» ближайший.

Почему наивная реализация $O(\text{источников} \cdot R \cdot C)$ — медленнее

Можно было бы запустить отдельный BFS из каждого источника и для каждой клетки взять минимум. Но это $O(\text{источников} \cdot (R \cdot C))$, что при максимуме источников = $R \cdot C$ даёт квадрат от размера сетки — $10^{12}$ операций для $1000 \times 1000$.

Multi-source BFS использует тот факт, что нам нужно одно и то же значение для каждой клетки — расстояние до ближайшего источника. Один проход обходом за $O(R \cdot C)$.

Код решения

Сложность: $O(R \cdot C)$ времени и памяти. Каждая клетка добавляется в очередь не более одного раза.

Что закрыли

Ступень 2 — умение переинициализировать BFS так, чтобы стартовать из набора вершин одновременно. Каркас не изменился; изменился только «нулевой шаг». Это принципиальный приём: при виде задачи «расстояние до ближайшего из X / Y / Z» — сразу думать про multi-source BFS, а не про N независимых обходов.

Следующий шаг — выйти за пределы «вершина = состояние» и научиться запускать BFS на расширенном графе.

---

Ступень 3 — CF ~2100 (BFS на расширенном состоянии)

Условие: «Кратчайший путь с собиранием ключей»

Дана прямоугольная сетка $R \times C$. Клетки бывают:

• . — проходимая клетка,
• # — стена,
• S — старт,
• E — финиш,
• строчные буквы a, b, ..., f — ключи (до 6 различных цветов; каждый цвет встречается не более одного раза),
• заглавные буквы A, B, ..., F — замки (соответствуют ключам того же цвета).

Перемещение — на 1 шаг в любую из 4 кардинальных сторон. Через стену пройти нельзя. Через замок цвета X пройти можно, только если уже собран ключ x. Через клетку с ключом проходить можно всегда; при первом проходе ключ автоматически добавляется в инвентарь.

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

Ограничения: $1 \le R, C \le 30$, число ключей $k \le 6$.

Пример. Сетка:

S . a A . E

Ключ a находится между стартом и замком A. Маршрут: $S \to . \to a$ (собрали ключ a) $\to A$ (можем пройти) $\to . \to E$. Длина — 5 шагов.

Что меняется в шаблоне

• Состояние: не клетка $(r, c)$, а тройка $(r, c, \text{маска собранных ключей})$. Маска — целое число от $0$ до $2^k - 1$, бит $i$ установлен ⟺ ключ $i$-го цвета собран.
• Расширение графа: одна и та же клетка $(r, c)$ существует в $2^k$ копиях — по одной на каждое состояние инвентаря. Переход по ребру меняет маску, если на новой клетке лежит ключ.
• Размер графа: $O(R \cdot C \cdot 2^k)$ состояний. При $R = C = 30$, $k = 6$ — это $30 \cdot 30 \cdot 64 = 57\,600$ состояний. BFS пробегает каждое состояние не более одного раза.
• Финиш: «достижение клетки $E$ с любой маской» (не нужно собирать все ключи; нужно только дойти до выхода).

Почему расширение состояния необходимо

Если попробовать запустить BFS только по координатам клетки, мы потеряем информацию о собранных ключах. Тогда замок будет либо «всегда непроходим» (никогда не достигнем выхода за ним), либо «всегда проходим» (нашли «путь», для которого по сюжету не хватало ключа). Оба варианта дают неверный ответ.

Расширение «(клетка) → (клетка, маска)» решает проблему: одна клетка в разных состояниях инвентаря — это разные узлы в расширенном графе. Из узла $(r, c, \text{mask})$ можно перейти в $(r', c', \text{mask}')$, где $\text{mask}'$ обновляется при подборе ключа.

Код решения

Сложность: $O(R \cdot C \cdot 2^K)$ времени и памяти. При $K = 6$, $R = C = 30$ — около $5.7 \cdot 10^4$ состояний, проходит мгновенно.

Что закрыли

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

---

Что нужно держать в голове при переходе между ступенями

Эта таблица — «карта местности» для тренировки. Её имеет смысл иметь под рукой в первые 2–3 недели прохождения полосы CF 1300–2100 на тегах bfs, shortest paths, graphs.

---

Типичные ловушки на каждой ступени

• Ступень 1. Использовать стек вместо очереди (получается DFS, который не считает расстояния). Обновлять dist[v] после извлечения, а не при добавлении в очередь — это ломает корректность для рёбер с одинаковым весом, если позднее найдётся «лучший» путь к v.
• Ступень 2. Запустить отдельный BFS из каждого источника и взять минимум — даёт квадратичную сложность вместо линейной. Забыть инициализировать dist[source] = 0 для всех источников, а не для первого.
• Ступень 3. Помечать посещённость только по координатам $(r, c)$, без учёта маски — теряется состояние инвентаря, ответ становится недостижим или некорректен. Перепутать «можно пройти через замок» и «можно пройти через ключ»: на ключе никаких ограничений, на замке — ограничение по биту маски.

---

План тренировки

Практический чек-лист:

1. Ступень 1. Решить самостоятельно. Цель — прочувствовать каркас BFS. Затем 3–5 задач полосы CF 1100–1400 с тегом bfs and dfs and similar (чистый BFS на простом графе).
2. Ступень 2. После уверенного шаблона ступени 1 — переход. Решить multi-source задачу. Затем 3–5 задач полосы CF 1500–1700: «волна одновременно из X источников», «время до затопления каждой клетки», «минимальное расстояние до ближайшей вершины-маркера».
3. Ступень 3. Самая нетривиальная. Перед ней полезно решить пару задач на «BFS с состоянием» средней сложности (CF 1800–2000). Затем — задача с расширением состояния. Если застреваем более 1 часа — разобрать ход решения по этой статье.
4. После ступени 3 — выйти на 0-1 BFS (рёбра весов 0 и 1, очередь заменяется на deque) и Dijkstra (произвольные неотрицательные веса, очередь становится приоритетной).

---

Итого

• Тема: BFS на невзвешенных графах.
• Траектория: CF ~1300 → ~1700 → ~2100, с расширением «вершина $\to$ источники $\to$ (вершина, маска)».
• Ключевое умение: не просто «помнить, как пишется BFS», а способность расширять состояние под задачу — добавлять источники, добавлять параметр инвентаря, переходить к 0-1 BFS / Dijkstra на следующей ступени.
• Типичная ловушка перехода: забыть, что пометка посещённости должна работать на расширенном состоянии, а не только на координатах вершины. На ступени 3 это самая частая причина WA.