↵
За последние три дня я почти полностью сосредоточился на BFS по матрицам. Вместо решения большого количества разных тем я старался разобраться именно в том, почему алгоритм работает, где появляются TLE и почему некоторые реализации оказываются значительно быстрее при тех же идеях.↵
↵
## мультистартовый BFS вместо множества отдельных обходов↵
↵
Главная идея, которую я наконец понял, — если источников несколько, не нужно запускать BFS отдельно от каждого.↵
↵
Изначально я рассматривал вариант, где после нахождения каждого источника запускался свой обход. Такой подход может проходить по одним и тем же клеткам много раз.↵
↵
Если источников $k$, то в худшем случае получается↵
↵
$$↵
O(k \cdot n \cdot m).↵
$$↵
↵
Правильный вариант — сразу добавить все источники в очередь, присвоить им расстояние 0 и выполнить только один BFS.↵
↵
```python↵
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))↵
```↵
↵
После этого волны распространяются одновременно от всех источников.↵
↵
Сложность становится↵
↵
$$↵
O(nm).↵
$$↵
↵
### где это применяется↵
↵
Такой приём встречается очень часто:↵
↵
- несколько выходов;↵
- несколько источников заражения;↵
- несколько пожаров;↵
- несколько стартовых вершин графа;↵
- поиск расстояния до ближайшего объекта.↵
↵
Если в условии написано «есть несколько одинаковых стартовых точек», почти всегда стоит подумать о мультистартовом BFS.↵
↵
---↵
↵
## почему первое найденное расстояние уже минимальное↵
↵
Ещё один момент, который я раньше понимал не до конца.↵
↵
BFS обрабатывает вершины слоями.↵
↵
Сначала обрабатываются все клетки с расстоянием 0.↵
↵
Потом — все клетки с расстоянием 1.↵
↵
Потом — расстояние 2 и так далее.↵
↵
Из-за этого, если вершина впервые получила значение↵
↵
```python↵
dist[nx][ny] = dist[x][y] + 1↵
```↵
↵
то более короткий путь уже не сможет появиться позже.↵
↵
Поэтому достаточно проверять только непосещённые клетки.↵
↵
```python↵
if dist[nx][ny] == -1:↵
dist[nx][ny] = dist[x][y] + 1↵
q.append((nx, ny))↵
```↵
↵
Это намного проще, чем постоянно пытаться улучшать расстояния.↵
↵
---↵
↵
## типичная ошибка↵
↵
Во время реализации я использовал конструкцию вида↵
↵
```python↵
if dist[nx][ny] > dist[x][y] + 1:↵
...↵
elif dist[nx][ny] == -1:↵
...↵
```↵
↵
Для обычного BFS она не нужна.↵
↵
Если очередь работает корректно, первая запись расстояния уже является оптимальной.↵
↵
Лишние проверки только усложняют код и могут запутать при отладке.↵
↵
---↵
↵
## небольшая диагностическая задача↵
↵
После блока по BFS я начал проверять базовые навыки на более простых задачах.↵
↵
Например, была задача на поиск самого длинного неубывающего непрерывного отрезка массива.↵
↵
Во время решения получилось несколько вариантов с WA.↵
↵
Полезный вывод оказался простым: перед тем как менять код, стоит проверить несколько крайних случаев вручную:↵
↵
- массив полностью возрастающий;↵
- массив полностью убывающий;↵
- ответ заканчивается последним элементом;↵
- несколько максимальных отрезков одинаковой длины.↵
↵
Именно такие тесты чаще всего находят ошибки в индексах и обновлении ответа.↵
↵
---↵
↵
## что дальше↵
↵
Следующая тема, которую уже начали обсуждать, — задачи, где сначала нужно вычислить время распространения чего-либо мультистартовым BFS, а затем использовать эти расстояния во втором обходе (например, человек и распространяющийся пожар).↵
↵
Такие задачи уже требуют не только знания BFS, но и аккуратной работы со временем прихода в каждую клетку
↵
During the last three days I focused almost entirely on BFS on grids. Instead of solving many unrelated problems, I tried to understand why the algorithm works, where TLE comes from, and why some implementations are much faster despite using the same idea.↵
↵
## multi-source BFS instead of many separate searches↵
↵
The biggest takeaway was that if there are multiple sources, you should not run BFS from each of them independently.↵
↵
My initial idea was to launch a separate BFS every time I found a new source. This may traverse the same cells many times.↵
↵
If there are $k$ sources, the worst-case complexity becomes↵
↵
$$↵
O(k \cdot n \cdot m).↵
$$↵
↵
The correct approach is to put all sources into the queue at once, assign distance 0 to each of them, and run a single BFS.↵
↵
```python↵
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))↵
```↵
↵
Now all waves expand simultaneously from every source.↵
↵
The complexity becomes↵
↵
$$↵
O(nm).↵
$$↵
↵
### where this technique is useful↵
↵
This pattern appears in many problems:↵
↵
- multiple exits;↵
- multiple infection sources;↵
- multiple fires;↵
- multiple starting vertices;↵
- distance to the nearest object.↵
↵
Whenever a statement contains several equivalent starting points, multi-source BFS is often the right idea.↵
↵
---↵
↵
## why the first discovered distance is already optimal↵
↵
Another concept I finally understood is why BFS never needs to improve distances later.↵
↵
BFS processes vertices layer by layer.↵
↵
First all vertices with distance 0.↵
↵
Then all vertices with distance 1.↵
↵
Then distance 2, and so on.↵
↵
Therefore, if a vertex first receives↵
↵
```python↵
dist[nx][ny] = dist[x][y] + 1↵
```↵
↵
no shorter path can appear afterwards.↵
↵
That is why checking only unvisited vertices is enough.↵
↵
```python↵
if dist[nx][ny] == -1:↵
dist[nx][ny] = dist[x][y] + 1↵
q.append((nx, ny))↵
```↵
↵
This is much simpler than repeatedly trying to improve distances.↵
↵
---↵
↵
## a common mistake↵
↵
During implementation I used logic similar to↵
↵
```python↵
if dist[nx][ny] > dist[x][y] + 1:↵
...↵
elif dist[nx][ny] == -1:↵
...↵
```↵
↵
For a standard BFS this is unnecessary.↵
↵
If the queue is processed correctly, the first assigned distance is already optimal.↵
↵
Extra checks only make the implementation harder to read and debug.↵
↵
---↵
↵
## a small diagnostic problem↵
↵
After finishing this BFS block I started reviewing some basic algorithmic skills.↵
↵
One of the tasks was to find the longest non-decreasing contiguous subarray.↵
↵
I produced several Wrong Answers before getting it right.↵
↵
A useful lesson was to manually test edge cases before changing the implementation:↵
↵
- the whole array is non-decreasing;↵
- the whole array is decreasing;↵
- the answer ends at the last element;↵
- several longest segments have the same length.↵
↵
These cases often reveal indexing mistakes and incorrect answer updates.↵
↵
---↵
↵
## what's next↵
↵
The next topic we have already started discussing is problems where you first compute the spreading time with a multi-source BFS and then use those distances in a second traversal (for example, a person escaping from a fire).↵
↵
These problems require not only BFS itself but also careful reasoning about arrival times for every cell.
