Hi everyone!

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

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.

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

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

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

no shorter path can appear afterwards.

That is why checking only unvisited vertices is enough.

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

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.