Path Reconstruction

Finding the shortest path length is easy --- BFS gives you that for free. But most problems don't just want the distance. They want the actual path: the sequence of moves that gets you from A to B. This is where beginners fumble. They run BFS, get the distance, then realize they have no way to recover which cells they used. The fix is simple, but you have to plan for it before you start the BFS.

The Problem: CSES Labyrinth

Path traced back from destination to source using parent pointers

Parent pointer grid showing direction to previous cell in BFS tree

Input: An \(H \times W\) grid. A is the start, B is the end, . is floor, # is wall. Find the shortest path from A to B and print the directions as a string of U, D, L, R characters. If no path exists, print NO.

BFS finds the shortest distance. But we need more: the actual sequence of moves.

Parent Tracking on Grids

In Chapter 1, you recorded parent[v] = u during BFS to reconstruct paths on adjacency-list graphs. On grids, the idea is identical, but the storage is different.

Option 1: Store the direction. For each cell \((r, c)\), record which direction you came from to reach it. Use the index into your dx/dy arrays.

int par[1005][1005]; // par[r][c] = direction index d

When BFS reaches (nr, nc) from (r, c) using direction d, set par[nr][nc] = d.

Option 2: Store the parent coordinates. For each cell, record the (pr, pc) coordinates of the cell you came from.

pair<int,int> par[1005][1005];

Option 1 is cleaner for grids because you directly get the direction character for output. Option 2 requires computing the direction from the coordinate difference during backtracking.

BFS with Direction Recording

Here's the BFS. The only addition compared to plain BFS is par[nr][nc] = d.

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char dirChar[] = {'R', 'L', 'D', 'U'};

memset(dist, -1, sizeof(dist));
memset(par, -1, sizeof(par));
dist[sr][sc] = 0;
queue<pair<int,int>> q;
q.push({sr, sc});

while (!q.empty()) {
    auto [r, c] = q.front(); q.pop();
    for (int d = 0; d < 4; d++) {
        int nr = r + dx[d], nc = c + dy[d];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W
            && dist[nr][nc] == -1 && grid[nr][nc] != '#') {
            dist[nr][nc] = dist[r][c] + 1;
            par[nr][nc] = d;
            q.push({nr, nc});
        }
    }
}

Notice that dirChar maps direction index to output character. dx[0]=0, dy[0]=1 means moving right, so dirChar[0]='R'. The mapping between direction arrays and character arrays must be consistent.

Gotcha. Initialize par to \(-1\). The start cell has no parent, and you'll use this sentinel to know when backtracking is done.

Backtracking the Path

After BFS completes, walk backward from the end cell (er, ec) to the start cell (sr, sc) using the par array.

At each cell (r, c), par[r][c] tells you the direction d used to arrive at this cell. The previous cell's coordinates are (r - dx[d], c - dy[d]) --- reverse the direction to go back.

if (dist[er][ec] == -1) {
    cout << "NO\n";
} else {
    cout << "YES\n";
    cout << dist[er][ec] << "\n";

    string path;
    int r = er, c = ec;
    while (r != sr || c != sc) {
        int d = par[r][c];
        path += dirChar[d];
        r -= dx[d];
        c -= dy[d];
    }
    reverse(path.begin(), path.end());
    cout << path << "\n";
}

The path is built in reverse (end to start), so you reverse it before printing.

Full Worked Example

Shortest path on grid highlighted in blue from start to end

Grid (5x7):

#######
#A..#.#
#.#...#
#...#B#
#######

Start: A at (1,1). End: B at (3,5).

BFS Expansion

Distance	Cells reached	Direction recorded
0	(1,1)	---
1	(1,2), (2,1)	par[1][2]=R, par[2][1]=D
2	(1,3), (2,3)*, (3,1)	par[1][3]=R, par[3][1]=D
3	(2,3), (3,2)	par[2][3]=D, par[3][2]=R
4	(2,4), (3,3)	par[2][4]=R, par[3][3]=D
5	(2,5), (3,5)**	par[2][5]=R

*Reached from (1,3) going down, but also reachable from (2,1) going right. BFS takes whichever arrives first.

**Wait --- can (3,5) be reached? Let me re-check. (2,5) is reached at distance 5 from (2,4). Then (3,5) is reached from (2,5) going down at distance 6. Also check (3,3) at distance 4, then (3,4) --- but (3,4) is #. So the path goes through column 5.

Let me redo this carefully.

Corrected BFS Trace

Grid indices:
(1,1)=A  (1,2)=.  (1,3)=.  (1,4)=#  (1,5)=.
(2,1)=.  (2,2)=#  (2,3)=.  (2,4)=.  (2,5)=.
(3,1)=.  (3,2)=.  (3,3)=.  (3,4)=#  (3,5)=B

Step	Popped	Distance	New cells pushed	par recorded
1	(1,1)	0	(1,2), (2,1)	par[1][2]=0(R), par[2][1]=2(D)
2	(1,2)	1	(1,3)	par[1][3]=0(R)
3	(2,1)	1	(3,1)	par[3][1]=2(D)
4	(1,3)	2	(2,3)	par[2][3]=2(D)
5	(3,1)	2	(3,2)	par[3][2]=0(R)
6	(2,3)	3	(2,4)	par[2][4]=0(R)
7	(3,2)	3	(3,3)	par[3][3]=0(R)
8	(2,4)	4	(2,5)	par[2][5]=0(R)
9	(3,3)	4	---	(3,4) is wall
10	(2,5)	5	(1,5), (3,5)	par[3][5]=2(D)

Distance to B: 6. (3,5) is reached at distance 6 from (2,5) at distance 5.

Backtracking

Current cell	par[r][c]	Direction char	Previous cell
(3,5)	2 (D)	D	(2,5)
(2,5)	0 (R)	R	(2,4)
(2,4)	0 (R)	R	(2,3)
(2,3)	2 (D)	D	(1,3)
(1,3)	0 (R)	R	(1,2)
(1,2)	0 (R)	R	(1,1) = start

Collected (reversed order): D, R, R, D, R, R

Reversed: R, R, D, R, R, D

Path: from (1,1) go Right to (1,2), Right to (1,3), Down to (2,3), Right to (2,4), Right to (2,5), Down to (3,5). Six moves, shortest path.

Why This Always Gives the Shortest Path

BFS visits cells in order of increasing distance. The first time a cell is reached, it's reached via a shortest path. The par value recorded at that moment traces back along that shortest path. Later arrivals at the same cell are ignored because dist[nr][nc] != -1.

Key insight. BFS guarantees that par records a shortest-path tree. Every cell's parent leads one step closer to the source along a shortest route. Backtracking through par is guaranteed to produce a shortest path.

When No Path Exists

If BFS finishes without reaching the target, dist[er][ec] remains \(-1\). Print NO. No special handling needed --- the BFS simply never pushes the target into the queue because no sequence of valid moves reaches it.

#####
#A#B#
#####

BFS from (1,1) can only reach (1,1) itself. dist[1][3] stays \(-1\). Output: NO.

Implementation Checklist

Common mistakes and how to avoid them:

Mistake	Fix
Forgetting to reverse the path	Build backward, then `reverse()`
Direction arrays and char arrays out of sync	Define them side by side: `dx={0,0,1,-1}`, `dirChar={'R','L','D','U'}`
Not handling the "no path" case	Check `dist[er][ec] == -1` before backtracking
Backtracking past the start cell	Loop condition: `while (r != sr \\|\\| c != sc)`
Using DFS instead of BFS	DFS finds a path, not the shortest path

Gotcha. If you use DFS for path-finding on a grid, you'll find a path, but it won't be shortest. Only BFS guarantees shortest paths on unweighted grids. This is the most common mistake in contest submissions.

Alternative: Store Parent Coordinates

Instead of storing direction indices, store the coordinates of the parent cell directly.

pair<int,int> par[1005][1005];

// During BFS:
par[nr][nc] = {r, c};

// Backtracking:
int r = er, c = ec;
string path;
while (r != sr || c != sc) {
    auto [pr, pc] = par[r][c];
    if (pr == r - 1) path += 'D';
    else if (pr == r + 1) path += 'U';
    else if (pc == c - 1) path += 'R';
    else path += 'L';
    r = pr; c = pc;
}
reverse(path.begin(), path.end());

This works but requires computing the direction from coordinate differences during backtracking. The direction-index approach is cleaner.

Connecting to CSES Monsters

In Lesson 3, you learned multi-source BFS for CSES Monsters. That problem also requires path reconstruction --- you need to print the player's escape route. The technique is identical: record par[nr][nc] = d during the player's BFS, then backtrack from the boundary cell the player reaches.

The only difference: you run two BFS passes (monsters then player) and only reconstruct the path from the second one.

Exercises

Multiple shortest paths. On a 4x4 grid with no walls, how many distinct shortest paths exist from (0,0) to (3,3)? BFS gives you one of them. Can you modify the algorithm to count all shortest paths? (Hint: instead of par, maintain a count.)
Longest path. Can you find the longest path between two cells in a grid using BFS? Why or why not? What makes longest-path fundamentally harder than shortest-path?
Bidirectional BFS. Run BFS simultaneously from both A and B. When the two wavefronts meet, you've found the shortest path. Implement this and compare the number of cells visited versus standard BFS. When is bidirectional BFS faster?
Monsters path. Solve CSES Monsters completely: print YES, the path length, and the direction string. Remember to handle the edge case where A is already on the boundary.

Problems

Problem	Link	Difficulty
CSES Labyrinth	cses.fi/problemset/task/1193	Easy
LC 1091 --- Shortest Path in Binary Matrix	leetcode.com/problems/shortest-path-in-binary-matrix	Medium
LC 490 --- The Maze	leetcode.com/problems/the-maze	Medium
CSES Monsters	cses.fi/problemset/task/1194	Medium