Multi-source BFS on grids in Python

Why this matters

Many real problems look like a map divided into squares. Some squares start in a special state, such as a rotten fruit, a fire, a gate or a sensor. The special state spreads to neighbouring squares, one step at a time. The questions are usually these: how long until everything is affected, and how far is each square from the nearest start?

A breadth-first search, or BFS, answers both questions in one pass. It is the standard tool for finding the fewest steps between cells on a grid. This lesson uses BFS, but it starts the search from many cells at the same moment. That version is called a multi-source BFS. It is short to write, and it appears often in interview questions about grids.

You need to know what a queue is and how collections.deque works. You also need to know that a grid in Python is a list of lists, so grid[r][c] reads row r and then column c. The lesson does not re-teach the queue from the earlier lessons in this module, and it does not cover graph search in general, which comes later in the course.

The idea in plain words

A grid is a rectangle of cells. Each cell has a row number and a column number. In this lesson we count row numbers from the top and column numbers from the left, starting at 0. The cell at row 2, column 1 is written (2, 1). In Python, that pair is a tuple, a small group of values that cannot be changed after it is made.

A cell has up to four neighbours: the cell above, below, left and right of it. Diagonal cells are not neighbours here. Cells on the edge of the grid have fewer neighbours, because the grid stops there.

A BFS starts at one cell and explores in layers. Layer 0 is the start cell. Layer 1 is every neighbour of the start cell. Layer 2 is every new cell next to a layer 1 cell, and so on. Each layer is one step further from the start. A queue keeps the cells in the right order: the cells of the current layer are removed first, and the cells they discover go to the back of the line.

A BFS that starts from one cell gives the number of steps from that cell to every other cell. A multi-source BFS asks a slightly different question. The start cells are all cells that begin in the special state. The answer for each cell is the number of steps to the nearest start cell.

One source, then many

There is a slow way to solve the many-source version. Run a separate BFS from each start cell, then combine the answers. That works, but it repeats the same work many times. A grid with a thousand rotten fruits would need a thousand searches.

The fast way puts every start cell into the queue before the search begins. Every start cell is layer 0. When the BFS takes one step, all of them spread at the same time. A cell is reached by whichever start cell is closest to it, because the first time a cell is added to the queue is the shortest distance to it. The whole grid is visited once, so the cost is proportional to the number of cells.

Here is the rule to remember: put all the sources in the queue first, then run one ordinary BFS.

Worked example 1: rotting oranges

Imagine a box of oranges on a table divided into a 3 by 3 grid. Each cell holds one of three values:

• 0 means an empty cell.
• 1 means a fresh orange.
• 2 means a rotten orange.

Every minute, a fresh orange next to a rotten orange becomes rotten. The task is to find how many minutes pass before no fresh oranges are left. If some fresh orange can never be reached, the answer is -1.

Here is the starting grid, written as a list of lists:

[[2, 1, 1],
 [1, 1, 0],
 [0, 1, 1]]

The rotten orange is at (0, 0).

Work through it by hand one minute at a time. Each minute, every rotten orange turns its fresh neighbours rotten. All of this happens at once, so a cell that turns rotten in minute 2 cannot spread the rot until minute 3.

Minute 1: rotten from (0,0) reach (0,1) and (1,0)     fresh left: 4
Minute 2: rotten from (0,1) reach (0,2); from (1,0) reach (1,1)     fresh left: 2
Minute 3: rotten from (1,1) reach (2,1)     fresh left: 1
Minute 4: rotten from (2,1) reach (2,2)     fresh left: 0

Four minutes pass before the last fresh orange turns, so the answer is 4.

Notice what the minutes are. Minute 1 is one BFS layer, minute 2 is the next layer, and so on. The queue never needs to know the distance of each cell. The layer that is being processed tells the code which minute it is.

The code

The program below is complete. It stores the grid as a list of lists. The queue is a deque from the collections module. Each queue entry is a tuple with the row and the column. The program also contains the gate example from the next section, and it prints the output shown after the explanation.

The code has five parts, and each one matches an idea from above.

The first loop puts every rotten orange into the queue and counts the fresh ones. This is the multi-source step. The counter fresh tells us at the end whether any fresh orange was missed.

The while loop runs one layer per pass. The line size = len(queue) records how many cells belong to the current layer before any new cells are added. The inner for loop removes exactly size cells, so the cells added during this pass wait for the next one. Without this snapshot, the code would mix layers and count the wrong minutes.

The direction loop looks at the four neighbours. The if line with 0 <= nr < rows is a chained comparison. Python reads it as two checks in one line: nr is at least 0, and nr is less than rows. The not in front means that a neighbour outside the grid is skipped. Empty cells, walls and rotten oranges are also skipped, because only fresh cells pass the second if.

When a fresh orange is found, the code sets it to rotten at once, lowers fresh by one and adds it to the queue. Setting it at this moment is what stops the same cell from being added twice.

The minutes counter goes up after each layer. The final line returns -1 if some fresh orange was never reached.

The function changes the grid it is given. After the call, first holds the final state, not the starting state. Keep this in mind when you call a function twice on the same list.

The output of the program is:

oranges 1: 4
oranges 2: -1
oranges 3: 0
[4, -1, 0, 1]
[3, 2, 1, -1]
[-1, 3, -1, 0]
[4, 3, 2, 1]
farthest reachable cell: 4

The second grid is:

[[2, 1, 1],
 [0, 1, 1],
 [1, 0, 1]]

The orange at (2, 0) has only empty cells as neighbours, so the rot can never reach it. The count of fresh oranges never reaches zero, and the answer is -1.

Why deque and not a plain list

A plain Python list can be used as a queue with append to add at the back and pop(0) to remove from the front. It gives the right answers, but pop(0) moves every remaining item one place to the left. The longer the queue, the more work each removal costs.

collections.deque (read "deck") is built for this job. append adds to the back, and popleft removes from the front, and neither one moves the other items. Use deque for any queue in Python.

Worked example 2: distance to the nearest gate

The second example is a map with gates and walls. Each cell holds one of three kinds of value:

• A wall cannot be entered. Use -1 for it.
• A gate is a start cell. Use 0 for it, because the distance from a gate to itself is 0.
• An open cell is a room that has not been reached yet. Use math.inf for it.

Python integers have no largest value, so the code uses math.inf, which is a float (a number with a decimal part) that is larger than any integer. The Java version of this lesson used Integer.MAX_VALUE for the same job. Any open cell that stays at math.inf after the search was never reached.

The task is to write the distance from the nearest gate into every open cell. Open cells that cannot be reached keep the value math.inf.

Here is the starting map, with OPEN standing for math.inf:

OPEN WALL GATE OPEN
OPEN OPEN OPEN WALL
WALL OPEN WALL GATE
OPEN OPEN OPEN OPEN

The idea is the same as in the first example. Every gate goes into the queue at the start. Then the search moves outward one layer at a time. The first time a search reaches an open cell, it is the nearest gate, so that is the value the cell keeps.

The main change is that the distance is stored in the grid itself. The cell's value is the distance from the cell that found it, plus one. Because the value is no longer math.inf, the cell counts as visited. The same test that checks for fresh oranges now checks for open cells.

The function distance_to_gates in the program above has no size snapshot. It does not count minutes or layers. The distance is already in each cell, so the code only needs to know which cell it is working on. The queue still keeps the cells in order of distance, because every cell added is one step further than the cell that added it.

The program prints the map after the search:

[4, -1, 0, 1]
[3, 2, 1, -1]
[-1, 3, -1, 0]
[4, 3, 2, 1]

Check one value by hand. The cell in row 0, column 0 has value 4. Its nearest gate is at row 0, column 2. The path goes down to row 1, column 2, then left to row 1, column 1, then left to row 1, column 0, then up to row 0, column 0. That is four steps, so the value is 4. The path cannot go through the wall at row 0, column 1, and the gate at row 2, column 3 is farther away.

Harder example: the farthest reachable cell

The third example uses the same map. The question is now: which open cell is the farthest from any gate? This is a common follow-up question in interviews. The answer is the largest distance written into the grid, but the code must skip the walls, the gates and any open cell that stayed at math.inf.

farthest = 0
for row in gates:
    for value in row:
        if value != WALL and value != OPEN and value > farthest:
            farthest = value
print("farthest reachable cell:", farthest)

For the map above, the program prints:

farthest reachable cell: 4

Two cells have the value 4, at row 0, column 0 and at row 3, column 0. The check value != OPEN matters here. Without it, a cell that no gate can reach would keep the value math.inf. Because math.inf is larger than every number, the answer would be infinity, which means nothing for this question.

Edge cases

Three small cases catch most of the bugs in this kind of code.

When the grid has no rotten oranges and some fresh oranges, the queue is empty from the start. The while loop never runs. The function returns -1 because fresh is still above zero. This is the correct answer, because nothing can spread.

When the grid has no fresh oranges, the function returns 0 at once. The loop condition fresh > 0 is false before the first pass, so no minutes are counted.

When the grid has no gates, every open cell keeps math.inf. A map with no gates and only open cells prints this:

[[inf, inf], [inf, inf]]

The rule behind all three cases is the same: the answer must match what the grid really says, not what the loop happened to do.

Common mistakes

Checking the bounds after reading the cell

The code must check that the row and column are inside the grid before it reads grid[nr][nc]. Python handles the two sides of the grid differently, so the mistake shows up in two ways.

If the check for the bottom or right edge is missing, Python stops with an error. In a 2 by 2 grid, the row index 2 is past the end, and the error looks like this. The program catches it and prints the message on one line:

bottom edge: IndexError list index out of range

If the check for the top or left edge is missing, nothing stops the program. A negative index in Python counts from the end of the list, so index -1 is the last row. For the 2 by 2 grid [[1, 2], [3, 4]], the expression grid[-1][0] gives the value in the bottom row, and no error is raised:

negative index: 3

The value 3 comes from the bottom row, not from anything above the top row. The bug does not raise an error, so it is harder to find. The fix is the chained comparison 0 <= nr < rows, which checks both sides.

Returning the minute count without checking for fresh oranges

The count of minutes is not the answer when some oranges were never reached. In the second grid from the first example, the search stops when the queue is empty. If the function returns minutes at that point, it reports a number when it should report -1. A version that skips the final fresh == 0 check prints this for the second grid:

returns always: 5

The correct answer is -1. The extra minute comes from the last pass of the loop. The cell at row 2, column 2 is rotten in minute 4. The next pass of the loop looks at its neighbours, finds nothing fresh to turn, and still adds one to minutes. The check fresh == 0 at the end prevents this from becoming the answer.

Marking a cell when it is removed instead of when it is added

Some people set a cell to rotten when they take it out of the queue. The search then adds the same fresh cell several times, because two rotten cells can both find it before either one removes it. The queue grows and the same work is done twice. The count fresh also goes down twice for one orange, so the final answer can be wrong. The fix is to change the cell as soon as it is added, as the code above does.

Starting a separate search for each source

A program that runs one BFS from the first rotten orange, then another from the second, and so on, is slow. On a large grid, it may take far too long. It can also give the wrong answer if the results are combined in the wrong way. The fix is the rule from earlier: put every source in the queue before the first step.

Counting cells instead of layers

A loop written as while queue: that adds one to minutes every time it removes a cell counts cells, not minutes. Two cells in the same layer would add two minutes. The size snapshot is what turns the queue into layers.

Building a grid with * on a list

A common way to make a grid is [[0] * cols] * rows. It looks right, but every row is the same list object, so changing one cell changes the same cell in every row. Here is the output of that line and of the safe version, after setting the cell at row 0, column 0 to 7:

shared rows: [[7, 0], [7, 0]]
separate rows: [[7, 0], [0, 0]]

The safe version builds each row separately with a list comprehension: [[0] * cols for _ in range(rows)]. Use it for every grid you create.

Using pop(0) as the queue

Removing from the front of a plain list with pop(0) gives the right answer, but it moves every remaining item. On a big grid, the queue can hold thousands of cells, and each removal then does a lot of moving. Use collections.deque and popleft() instead, as the code above does.

Practice

Try each exercise on paper first, then check your answer with the code in this lesson.

Exercise 1

Find the answer for this single row of oranges. Use the rules from the first example.

[[2, 2, 0, 1]]

Show the answer

The answer is -1. The rotten oranges at (0, 0) and (0, 1) have no fresh neighbour that they can reach. The cell at (0, 2) is empty, and it is the only thing between them and the fresh orange at (0, 3). The program returns -1 for this grid.

Exercise 2

Find the answer for this grid. One rotten orange sits in the middle.

[[1, 1, 1],
 [1, 2, 1],
 [1, 1, 1]]

Show the answer

The answer is 2. In minute 1 the centre spreads to the four cells above, below, left and right of it. In minute 2 those cells spread to the four corners. Every fresh orange is then rotten, so the answer is 2. The program returns 2.

Exercise 3

Fill in the distances for this 2 by 2 map. The gate is at the top left, and the other three cells are open.

GATE OPEN
OPEN OPEN

Show the answer

The distances are 1 for the cell to the right of the gate, 1 for the cell below the gate, and 2 for the bottom right cell. The grid after the search is [[0, 1], [1, 2]]. Both the cell to the right and the cell below are one step from the gate, and the bottom right cell is two steps away through either of them.

Exercise 4

Look at this map after the search has run. Each row is printed as a list of numbers, with -1 for walls.

[0, -1, 6]
[1, -1, 5]
[2, 3, 4]

What is the distance from the gate to the cell at row 0, column 2? Explain which path the search uses.

Show the answer

The distance is 6. The gate is at row 0, column 0. The search cannot pass the walls in column 1 of rows 0 and 1, so it goes down column 0 to row 2, across row 2 to column 2, and then up column 2 to row 0. That path has six steps: down two, across two, and up two.

Exercise 5

Explain in your own words why the size snapshot is needed in minutes_to_rot, and what would go wrong without it.

Show the answer

The snapshot records how many cells belong to the current layer before any new cells are added. The inner loop removes exactly that many cells. Without the snapshot, a cell added in this pass would be removed in the same pass, so its neighbours would spread in the same minute. The minute counter would no longer match the layers of the search.

Summary

• A multi-source BFS puts every starting cell in the queue before the first step, so all sources spread at the same time.
• Each pass through the queue is one step of distance, which is why a snapshot of the queue size gives the minute count.
• Storing the distance in the grid itself marks a cell as visited and gives the answer at the same time.
• Mark a cell as soon as it is added to the queue, so it is never added twice.
• Check the grid bounds before reading a cell, and check at the end whether anything was left unreached.