Breadth-First Search
GOALUse a queue to find the length of the shortest path.
Breadth-first search looks at everything one step away, then everything two steps away. That gives it a remarkable property: when every move costs the same, BFS finds the SHORTEST path. It is the workhorse of grid problems for exactly that reason.
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int rows = 3, cols = 4;
vector<vector<int>> dist(rows, vector<int>(cols, -1));
queue<pair<int,int>> q;
dist[0][0] = 0;
q.push({0, 0});
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
while (!q.empty()) {
pair<int,int> cell = q.front();
q.pop();
int r = cell.first, c = cell.second;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
cout << dist[2][3] << endl;
return 0;
}5
//LINE BY LINE
Watch it run
Only the starting cell is known: dist[0][0] = 0.
Why BFS finds the shortest path
BFS looks at every node one step away, then everything two steps away. So the FIRST time it reaches a node, that must be the shortest route — a shorter one would have been found in an earlier wave.
The guarantee holds only while every step costs the SAME. With different edge lengths the idea of a wave breaks down and you need Dijkstra.
When to mark a cell
This is the most common performance bug in BFS. Mark a cell when you PUSH it, not when you pop it.
// wrong — the same cell enters the queue many times
while (!q.empty()) {
auto cur = q.front(); q.pop();
if (seen[cur]) continue;
seen[cur] = true;
...
}
// right — it can only ever enter once
dist[next] = dist[cur] + 1;
q.push(next); // marked and queued togetherThe wrong version still gives the right answer, but one cell enters the queue many times and on a large grid it times out.