Multi-source BFS on grids

Why this matters

A grid is a table of cells. Each cell has a row and a column, and you can move from a cell to one of its four neighbours: up, down, left or right. Many problems look like this. A map of rooms, a picture made of pixels and a board game all use grids.

A common question about a grid is "how far is each cell from the closest special cell?" For example, a city planner wants to know how far each house is from the nearest fire station. A game wants to know how many minutes it takes for fire to spread to every tile. A puzzle wants to know how many steps a robot needs to reach the nearest gate.

Breadth-first search, usually shortened to BFS, answers this kind of question. The earlier lessons in this module built the queue and the stack that BFS uses. This lesson does not teach the queue again. It takes the standard BFS and changes one thing: it starts from many cells at the same time. That change is called multi-source BFS. The "source" is a starting cell.

The idea in plain words

A queue is a line where the first item in is the first item out. You add items at the back and remove them from the front. In C++ the standard library gives you this as std::queue.

BFS uses the queue to explore a grid in rings. Picture a stone dropped into still water. The ripple grows outward one ring at a time. Every cell in the first ring is one step from the stone. Every cell in the second ring is two steps away, and so on. A queue produces this order naturally. It handles all the cells at distance 1 before it handles any cell at distance 2.

Here is the rule for BFS on a grid. Put the start cell in the queue and mark its distance as 0. Then repeat until the queue is empty:

1. Take the cell at the front of the queue.
2. Look at its four neighbours.
3. For each neighbour that is inside the grid, is not a wall and has not been reached yet, set its distance to one more than the current cell, and add it to the back of the queue.

A cell that has not been reached yet has no distance. This lesson uses -1 for "not reached yet". The first time a neighbour is reached, its distance is fixed. Because BFS handles cells in ring order, that first distance is the shortest one.

Multi-source BFS changes only the start. Instead of putting one start cell in the queue, you put all of them in the queue at distance 0 before the loop begins. The ripples then grow from every start at once. A cell gets the distance of whichever ripple reaches it first, and that is the nearest start.

Example 1: distance to the nearest gate

A gate is a cell the robot can use to leave the grid. Walls are cells the robot cannot enter. Here is a grid with two gates, G, and walls, #. Empty cells are dots.

G..#.
.#...
...#G
.#...

The task is to compute, for every empty cell, the number of moves to the nearest gate. Walls get no number.

The code below does this. It is written to be read slowly, so each part has a name.

#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
 
struct Cell {
    int row;
    int col;
};
 
int main() {
    std::vector<std::string> grid = {
        "G..#.",
        ".#...",
        "...#G",
        ".#...",
    };
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    const int unknown = -1;
 
    std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, unknown));
    std::queue<Cell> q;
 
    // Put every gate in the queue before the loop starts.
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == 'G') {
                dist[r][c] = 0;
                q.push({r, c});
            }
        }
    }
 
    const int dr[] = {-1, 1, 0, 0};
    const int dc[] = {0, 0, -1, 1};
 
    while (!q.empty()) {
        Cell cur = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int nr = cur.row + dr[k];
            int nc = cur.col + dc[k];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] == '#') continue;
            if (dist[nr][nc] != unknown) continue;
            dist[nr][nc] = dist[cur.row][cur.col] + 1;
            q.push({nr, nc});
        }
    }
 
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == '#') {
                std::cout << std::setw(3) << "#";
            } else if (dist[r][c] == unknown) {
                std::cout << std::setw(3) << "?";
            } else {
                std::cout << std::setw(3) << dist[r][c];
            }
        }
        std::cout << '\n';
    }
}

The two arrays dr and dc hold the four moves. Index 0 is up, which is one row less. Index 1 is down. Index 2 is left and index 3 is right. The loop for (int k = 0; k < 4; ++k) tries each move in turn. The grid is stored as std::vector<std::vector<int>>, so dist[r][c] is the value in row r, column c. The printing code uses std::setw(3) from <iomanip> to give every number a field three characters wide, so the columns line up.

The bounds check is the line if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;. It stops the code from reading a cell outside the grid. The continue statement skips to the next move.

Compile and run it.

g++ -std=c++20 -Wall -g -o gates gates.cpp
./gates

The output is:

  0  1  2  #  2
  1  #  3  2  1
  2  3  4  #  0
  3  #  3  2  1

Check a few cells by hand. The gate at the top left is at row 0, column 0, so that cell has distance 0. The cell at row 0, column 2 is two moves to the right of it, and the walls in column 3 block the short way. The cell at row 0, column 4 is next to the gate at row 2, column 4, which is two moves away going down. The output says 2, which is correct. The cell at row 2, column 2 is reached from both gates, and the output says 4. Both gates are four moves away, so this cell is a tie. Example 3 shows which gate the code picks.

Look at the walls too. The printing code writes # for walls, so it does not need a number. A cell that stays at -1 would print as ?. In this grid every empty cell is reachable, so no ? appears.

Example 2: how long until every orange rots

The second example adds a time dimension. A grid holds three kinds of cell. A 0 is an empty cell. A 1 is a fresh orange. A 2 is a rotten orange. Each minute, every fresh orange next to a rotten one becomes rotten. The task is to return the number of minutes until no fresh orange is left. If some fresh orange can never rot, return -1.

The rotting spreads in rings, just like the gate example. The difference is that this time the answer is the number of rings, not the distance of one cell. So the code must know when one ring ends and the next begins. It does this by counting how many cells are in the queue at the start of each minute, and processing exactly that many.

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
 
// 0 = empty cell, 1 = fresh orange, 2 = rotten orange.
// Returns the number of minutes until no fresh orange is left, or -1.
int minutesToRot(std::vector<std::vector<int>> grid) {
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
 
    std::queue<std::pair<int, int>> q;
    int fresh = 0;
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == 2) q.push({r, c});
            if (grid[r][c] == 1) ++fresh;
        }
    }
 
    const int dr[] = {-1, 1, 0, 0};
    const int dc[] = {0, 0, -1, 1};
    int minutes = 0;
 
    while (!q.empty() && fresh > 0) {
        // One pass through the queue is one minute.
        int count = static_cast<int>(q.size());
        for (int i = 0; i < count; ++i) {
            auto [r, c] = q.front();
            q.pop();
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (grid[nr][nc] != 1) continue;
                grid[nr][nc] = 2;
                --fresh;
                q.push({nr, nc});
            }
        }
        ++minutes;
    }
 
    return fresh == 0 ? minutes : -1;
}
 
int main() {
    std::cout << minutesToRot({{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}) << '\n';
    std::cout << minutesToRot({{2, 1, 1}, {0, 1, 1}, {1, 0, 1}}) << '\n';
    std::cout << minutesToRot({{0, 2}}) << '\n';
    std::cout << minutesToRot({{1, 0}}) << '\n';
}

Several things here are new compared with example 1.

The line auto [r, c] = q.front(); is a structured binding, a C++17 feature that unpacks a pair into two named variables, r and c. The grid is passed by value, written std::vector<std::vector<int>> grid with no &. So the function gets its own copy and may change it freely. The code turns a fresh orange into a rotten one by writing grid[nr][nc] = 2. That write also acts as the "already reached" mark, because only cells equal to 1 are ever added to the queue.

The variable fresh counts the fresh oranges that are left. Each time one rots, fresh goes down by one. When fresh reaches zero, the answer is the number of minutes so far. If the queue becomes empty while fresh is still above zero, some orange is cut off from every rotten one, and the answer is -1.

The variable count is taken once at the start of each minute. Items added during the minute go to the back of the queue, and they must wait for the next minute. Reading the size at the start is what keeps the rings separate.

Compile and run it.

g++ -std=c++20 -Wall -g -o rotting rotting.cpp
./rotting

The output is:

4
-1
0
-1

The first grid has four minutes of rotting, and the program returns 4. The second grid has a fresh orange at the bottom left, next to an empty cell and a rotten cell that cannot reach it, so the answer is -1. The third grid has no fresh oranges, so the answer is 0. The fourth grid has a fresh orange and no rotten orange at all, so nothing can ever start to spread, and the answer is -1.

The last two cases show why the function checks fresh rather than returning minutes straight away. A grid with no rotten oranges has an empty queue at the start. Without the check, the answer would be 0 for the fourth grid, which says the job was done instantly. That is wrong.

Example 3: which gate is nearest

The third example keeps track of which source each cell's distance came from. In the gate grid, the gates are now named A and B. For every empty cell, the output shows the letter of the nearest gate and the distance to it.

The change is small. Each queue entry now carries an owner field. When a cell is reached, the owner of its parent is copied to it.

#include <iostream>
#include <queue>
#include <string>
#include <vector>
 
struct Entry {
    int row;
    int col;
    int owner;  // which gate this cell's distance comes from
};
 
int main() {
    std::vector<std::string> grid = {
        "A..#.",
        ".#...",
        "...#B",
        ".#...",
    };
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
 
    std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1));
    std::vector<std::vector<char>> owner(rows, std::vector<char>(cols, '?'));
    std::queue<Entry> q;
 
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            char ch = grid[r][c];
            if (ch == 'A' || ch == 'B') {
                dist[r][c] = 0;
                owner[r][c] = ch;
                q.push({r, c, ch});
            }
        }
    }
 
    const int dr[] = {-1, 1, 0, 0};
    const int dc[] = {0, 0, -1, 1};
 
    while (!q.empty()) {
        Entry cur = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int nr = cur.row + dr[k];
            int nc = cur.col + dc[k];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] == '#' || dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[cur.row][cur.col] + 1;
            owner[nr][nc] = static_cast<char>(cur.owner);
            q.push({nr, nc, cur.owner});
        }
    }
 
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == '#') {
                std::cout << " ##";
            } else {
                std::cout << ' ' << owner[r][c] << dist[r][c];
            }
        }
        std::cout << '\n';
    }
}

The owner grid is a second grid of the same size. It is separate from dist, so the distance and the label can be read on their own.

Compile and run it.

g++ -std=c++20 -Wall -g -o nearest nearest.cpp
./nearest

The output is:

 A0 A1 A2 ## B2
 A1 ## A3 B2 B1
 A2 A3 A4 ## B0
 A3 ## B3 B2 B1

Read the top right cell. Its label is B and its distance is 2. The gate B is at row 2, column 4, two moves down. The cell at row 2, column 2 is labelled A with distance 4. Gate B is also four moves away, by a path around the walls in column 3, so this cell is a tie and the code keeps the label A.

Ties need care. A cell that is exactly as far from both gates gets the label of whichever ripple reached it first. In this grid the cell at row 2, column 2 is tied, and the code labels it A. In general, the answer is one of the nearest gates, and which one depends on the order the queue was filled in. The code above fills the queue in row order, but that order is not a tie rule you can count on for every grid. If a problem asks for a specific tie rule, you must write that rule into the code, because BFS does not choose one by itself.

Why one queue works for all the sources

The key claim is that a cell's distance from the first ripple to reach it is its distance to the nearest source. Here is a short argument.

All the sources start in the queue at distance 0. Suppose the queue at some moment holds only cells with distance d and cells with distance d + 1. This is true at the start, because every item is at 0. When the front cell at distance d is processed, its new neighbours get distance d + 1, and they go to the back of the queue. The queue still holds distances d and d + 1 only, in that order. So the queue always has the cells in non-decreasing distance order.

Given that order, the first time a cell is touched, the distance written to it is the smallest possible. Any other route to it would have to reach a neighbour at distance d or more, and such a neighbour sits behind the cell in the queue. So a second route can never be shorter. The code marks a cell as reached the first time it is touched, and it never changes that mark.

This is the reason BFS is used and not depth-first search. A stack explores one long path before it tries others, so the first time it touches a cell is not necessarily the shortest route. The gate grid would then give wrong distances.

Common mistakes

Starting from only one source

The most common mistake is to put only one source in the queue, usually the first one found. The distances then come from that source only, and any cell that only the other source can reach stays at -1.

The program below puts only the left gate in the queue for the grid G.#.G. It then prints the distance of the cell at column 3 with the left gate alone and with both gates.

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
 
// Fills dist with steps from the gates. Only the gates listed in starts are queued.
std::vector<std::vector<int>> spread(const std::vector<std::string>& grid,
                                     const std::vector<std::pair<int, int>>& starts) {
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1));
    std::queue<std::pair<int, int>> q;
    for (auto [r, c] : starts) {
        dist[r][c] = 0;
        q.push({r, c});
    }
    const int dr[] = {-1, 1, 0, 0};
    const int dc[] = {0, 0, -1, 1};
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] == '#' || dist[nr][nc] != -1) continue;
            dist[nr][nc] = dist[r][c] + 1;
            q.push({nr, nc});
        }
    }
    return dist;
}
 
int main() {
    std::vector<std::string> grid = {"G.#.G"};
    auto wrong = spread(grid, {{0, 0}});
    auto right = spread(grid, {{0, 0}, {0, 4}});
    std::cout << "cell (0,3) with one gate: " << wrong[0][3] << '\n';
    std::cout << "cell (0,3) with two gates: " << right[0][3] << '\n';
}

Output:

cell (0,3) with one gate: -1
cell (0,3) with two gates: 1

The wall at column 2 blocks the left gate from reaching column 3. With only one gate in the queue, the cell is reported as unreachable, even though the right gate is one move away. The fix is to put every source in the queue before the loop starts, as the first example does.

Using a stack instead of a queue

If you replace std::queue with std::stack, the code still compiles, because both have push and pop. But a stack takes the most recently added cell, so the search runs deep before wide. The first time a cell is reached is then not guaranteed to be the shortest route, and the distances can be too large. The code will run and print numbers, so this mistake is easy to miss. Check the output on a small grid where you know the answer.

Counting minutes with the wrong loop

In example 2, the count variable is read once at the start of the minute. If you write for (int i = 0; i < q.size(); ++i) instead, the loop condition re-reads the size each time. New oranges are added to the back during the loop, so the loop processes them in the same minute. The answer can then be too small or too large.

Forgetting the bounds check

A row or column of -1 is a valid C++ integer, but it is not a valid index. Reading an index below 0 is undefined behaviour. The program may print a wrong number, crash, or do nothing visible. A plain heap array makes the mistake easy to see under AddressSanitizer, a checker that the compiler adds to the program. The program below reads one cell above row 0 of a 2 by 2 grid stored in one array.

#include <iostream>
 
int main() {
    // A plain heap array of 4 ints (a 2 by 2 grid stored in one row).
    int* grid = new int[4]{};
    int r = 0;
    int c = 0;
    // Missing bounds check: r - 1 becomes -1 when r is 0.
    int up = grid[(r - 1) * 2 + c];
    std::cout << up << '\n';
    delete[] grid;
}

Compile it with the sanitizer and run it:

g++ -std=c++20 -Wall -g -fsanitize=address,undefined -o oob_asan oob.cpp
./oob_asan

The output starts like this. Process numbers and memory addresses change on each run, and the paths are shortened here.

==193429==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6e930d7e0008
READ of size 4 at 0x6e930d7e0008 thread T0
    #0 0x55f751664557 in main oob.cpp:9
...
SUMMARY: AddressSanitizer: heap-buffer-overflow oob.cpp:9 in main

The report names line 9, the line that reads the bad index. The fix is the bounds check from example 1, placed before every read of grid.

Forgetting to include the queue header

If the file does not include <queue>, the compiler stops with an error. Here is the message for a file that uses std::queue but includes only <iostream> and <vector>.

nohdr.cpp: In function ‘int main()’:
nohdr.cpp:5:10: error: ‘queue’ is not a member of ‘std’
    5 |     std::queue<int> q;
      |          ^~~~~
nohdr.cpp:3:1: note: ‘std::queue’ is defined in header ‘<queue>’; this is probably fixable by adding ‘#include <queue>’

The compiler prints more errors after these, all from the same missing name. The note at the end gives the fix. Add #include <queue> at the top of the file.

Comparing a signed int with a size

The grid code uses int for row and column numbers, because the moves can go negative. The size() function of std::vector returns an unsigned type. Comparing the two triggers a warning under -Wall.

sign.cpp: In function ‘int main()’:
sign.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 |     for (int i = 0; i < row.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

The examples in this lesson convert once with static_cast<int>(grid.size()) and then compare ints only. Keep that habit, and read every warning that -Wall gives you.

Practice

Exercise 1

Work this out on paper, then check by running the first example. Given the grid below, what is the distance of each empty cell to the single gate G? Write the numbers in a grid, with # for walls.

G.#
..#
...

Show the answer.

Answer:

0 1 #
1 2 #
2 3 4

The walls in column 2 are the two # cells. The bottom right cell is at row 2, column 2. Its shortest route is down two cells and across two cells, which is 4 moves.

Exercise 2

Change gates.cpp so that it also prints how many empty cells were never reached. Use the rule that a wall is not an empty cell. The answer for the grid in example 1 is 0.

Show the answer.

Answer: after the BFS loop, count the cells that are not walls and still have distance -1.

int unreachable = 0;
for (int r = 0; r < rows; ++r) {
    for (int c = 0; c < cols; ++c) {
        if (grid[r][c] != '#' && dist[r][c] == unknown) ++unreachable;
    }
}
std::cout << "unreachable: " << unreachable << '\n';

The wall check matters. Without it, the walls would be counted, because walls also keep the value -1.

Exercise 3

What does minutesToRot return for the grid {{2, 2}, {2, 2}}? What does it return for {{0, 0}}? Explain both answers in one sentence each.

Show the answer.

Answer: the first grid has no fresh oranges, so fresh starts at 0, the loop never runs, and the function returns minutes, which is 0. The second grid has no oranges at all, so fresh is 0 and the answer is also 0. Both answers are 0 because nothing needs to rot.

Exercise 4

Write a function largestDistance that takes a distance grid, such as the one from example 1, and returns the biggest value in it. Ignore cells that hold -1. Test it on the grid {{0, 1, 2}, {1, -1, 3}}. The answer should be 3.

Show the answer.

Answer:

int largestDistance(const std::vector<std::vector<int>>& dist) {
    int best = 0;
    for (const auto& row : dist) {
        for (int d : row) {
            best = std::max(best, d);
        }
    }
    return best;
}

The -1 cells do not need a special case here. Since best starts at 0 and -1 is smaller than 0, the std::max call never picks it. It needs #include <algorithm> for std::max. Compiled and run with the test grid, the function prints 3.

Exercise 5

Explain in your own words why a cell reached by the queue for the first time gets its shortest distance. Use the phrase "rings" in your answer. Three or four sentences are enough.

Show the answer.

Answer: BFS handles cells in ring order, so every cell at distance 1 is taken from the queue before any cell at distance 2. When a cell is first reached, it is reached from a cell in the ring just before it. No cell in an earlier ring is still waiting, so no shorter route can arrive later. Marking the cell at that point is safe.

Summary

• Multi-source BFS puts every starting cell in the queue at distance 0 before the loop begins.
• A cell's distance is the number of moves to the nearest start, because the queue handles cells in ring order.
• To count minutes, read the queue size once at the start of each ring and process exactly that many cells.
• Mark a cell as reached the first time it is touched. Its first distance is the shortest one.
• Check bounds before every read of the grid, and read every warning from -Wall.