Multi-Source BFS

Concept

Multi-source BFS starts BFS from multiple source cells simultaneously. Instead of pushing one starting node, we push all sources into the queue at distance 0 before running BFS. This computes the shortest distance from any source to every cell in one pass.

When to Use

  • ▸Finding shortest distance from any of multiple sources (e.g., rotting oranges spreading)
  • ▸Flood fill from multiple starting points at once
  • ▸Problems where multiple events happen simultaneously and spread outward
  • ▸Two-BFS problems (e.g., water vs person racing in a maze)

Intuition

Imagine dropping multiple stones into a pond at the same time. Each stone creates ripples that expand simultaneously. Multi-source BFS does exactly this — all sources start expanding at step 0, and the BFS naturally handles which source reaches each cell first. No need to run BFS separately from each source.

Complexity

Time
O(M * N)
Space
O(M * N)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> grid(n, vector<int>(m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> grid[i][j];

    int di[]={0, 1, 0, -1};
    int dj[]={1, 0, -1, 0};

    queue<pair<int, int>> q;
    vector<vector<int>> visited(n, vector<int>(m, -1));

    // Push ALL sources first
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 2){
                q.push({i, j});
                visited[i][j] = 0;
            }
        }
    }

    // Then BFS
    while(!q.empty()){
        int i = q.front().first;
        int j = q.front().second;
        q.pop();

        for(int k = 0; k < 4; k++){
            int ii = i + di[k];
            int jj = j + dj[k];

            if(ii >= 0 && ii < n && jj >= 0 && jj < m && grid[ii][jj] == 1 && visited[ii][jj] == -1){
                q.push({ii, jj});
                visited[ii][jj] = visited[i][j]+1;
            }
        }
    }

    // Find max time (or check if any cell unreachable)
    int mx = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 1 && visited[i][j] == -1){
                cout << -1 << "\n";
                return 0;
            }
            mx = max(mx, visited[i][j]);
        }
    }

    cout << mx << "\n";

    return 0;
}

// Sample Input (Rotting Oranges):
// 3 3
// 2 1 1
// 1 1 0
// 0 1 1
//
// Sample Output:
// 4