The Shortest Path in a Maze (BFS)
BFS (breadth-first search) visits the cells in order of their distance from the start, so the first time it reaches the goal, it has reached it along the shortest path. In this task we compute the length of the shortest path and print the path itself.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
The task
A maze is an n × m matrix (n, m ≤ 1000) with the characters: S – start, E – end (the goal), . – a passage, # – a wall. In one step you move to a neighbouring cell (up, down, left, right). Print the smallest number of steps from S to E and the maze in which one shortest path is marked with stars. If there is no path, print -1.
Example
Input
4 6
S..#..
.#.#.#
.#...E
...##.Output
7
S**#..
.#*#.#
.#***E
...##.The idea of the solution
- Start BFS from the start. The array
distkeeps the distance of every cell from the start (−1 = not visited yet). - When a cell is put into the queue, its distance is the distance of the current cell plus 1, and the array
fromrecords the cell we came from. - When BFS finishes,
distof the goal is the length of the shortest path. The path is reconstructed backwards: from the goal, throughfrom, to the start.
Every cell enters the queue at most once, so the complexity is O(n · m). BFS gives the shortest path only when all the steps have the same cost; for different costs Dijkstra's algorithm (SR) is used.
Solution (C++)
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> maze(n);
for (auto &row : maze) cin >> row;
int sr = 0, sc = 0, er = 0, ec = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (maze[i][j] == 'S') { sr = i; sc = j; }
if (maze[i][j] == 'E') { er = i; ec = j; }
}
vector<vector<int>> dist(n, vector<int>(m, -1));
vector<vector<pair<int, int>>> from(n, vector<pair<int, int>>(m, {-1, -1}));
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
queue<pair<int, int>> q;
q.push({sr, sc});
dist[sr][sc] = 0;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == er && c == ec) break; // the goal has been reached along the shortest path
for (int s = 0; s < 4; s++) {
int nr = r + dr[s], nc = c + dc[s];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
if (maze[nr][nc] == '#' || dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
from[nr][nc] = {r, c};
q.push({nr, nc});
}
}
if (dist[er][ec] == -1) {
cout << -1 << endl;
return 0;
}
cout << dist[er][ec] << "\n";
// reconstructing the path backwards, without the start and the goal
auto [r, c] = from[er][ec];
while (!(r == sr && c == sc)) {
maze[r][c] = '*';
auto p = from[r][c];
r = p.first;
c = p.second;
}
for (auto &row : maze) cout << row << "\n";
return 0;
}
The order of the moves (up, down, left, right) determines which of several shortest paths will be printed; the length is always the same.
Variants of the task
- Several starts (e.g. a fire spreads from several cells): at the beginning all the starts are put into the queue with distance 0.
- Keys and doors: the state is not just a cell, but a cell + a set of keys – BFS over states.
- Moving like a knight (the chess knight): only the arrays of moves change.
- Set the distance when you put a cell into the queue, not when you take it out.
- When the only question is "is there a path", an array of visited cells is enough; for the length you need
dist, and for the path itself alsofrom. - BFS does not work for weighted graphs – use Dijkstra's algorithm there.
Check your knowledge
Open the quiz
Mini quiz: the shortest path
1. Why does BFS find the shortest path in a maze?
2. What is the array from for?
