Всем привет!

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

мультистартовый BFS вместо множества отдельных обходов

Главная идея, которую я наконец понял, — если источников несколько, не нужно запускать BFS отдельно от каждого.

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

Если источников $$$k$$$, то в худшем случае получается

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

from collections import deque

q = deque()

for i in range(n):
    for j in range(m):
        if a[i][j] == 2:
            dist[i][j] = 0
            q.append((i, j))

После этого волны распространяются одновременно от всех источников.

Сложность становится

где это применяется

Такой приём встречается очень часто:

• несколько выходов;
• несколько источников заражения;
• несколько пожаров;
• несколько стартовых вершин графа;
• поиск расстояния до ближайшего объекта.

Если в условии написано «есть несколько одинаковых стартовых точек», почти всегда стоит подумать о мультистартовом BFS.

почему первое найденное расстояние уже минимальное

Ещё один момент, который я раньше понимал не до конца.

BFS обрабатывает вершины слоями.

Сначала обрабатываются все клетки с расстоянием 0.

Потом — все клетки с расстоянием 1.

Потом — расстояние 2 и так далее.

Из-за этого, если вершина впервые получила значение

dist[nx][ny] = dist[x][y] + 1

то более короткий путь уже не сможет появиться позже.

Поэтому достаточно проверять только непосещённые клетки.

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

Это намного проще, чем постоянно пытаться улучшать расстояния.

типичная ошибка

Во время реализации я использовал конструкцию вида

if dist[nx][ny] > dist[x][y] + 1:
    ...
elif dist[nx][ny] == -1:
    ...

Для обычного BFS она не нужна.

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

Лишние проверки только усложняют код и могут запутать при отладке.

небольшая диагностическая задача

После блока по BFS я начал проверять базовые навыки на более простых задачах.

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

Во время решения получилось несколько вариантов с WA.

Полезный вывод оказался простым: перед тем как менять код, стоит проверить несколько крайних случаев вручную:

• массив полностью возрастающий;
• массив полностью убывающий;
• ответ заканчивается последним элементом;
• несколько максимальных отрезков одинаковой длины.

Именно такие тесты чаще всего находят ошибки в индексах и обновлении ответа.

что дальше

Следующая тема, которую уже начали обсуждать, — задачи, где сначала нужно вычислить время распространения чего-либо мультистартовым BFS, а затем использовать эти расстояния во втором обходе (например, человек и распространяющийся пожар).

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