C: breadth-first search on a grid with an array queue
Find the length of the shortest path through a maze using a queue stored in a plain array.
#include <stdio.h>
#define ROWS 3
#define COLS 4
int main(void) {
const char *grid[ROWS] = {"S.#.", "..#.", "...G"};
int dist[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
dist[r][c] = -1;
}
}
int queue_r[ROWS * COLS], queue_c[ROWS * COLS];
int head = 0, tail = 0;
queue_r[tail] = 0;
queue_c[tail] = 0;
tail++;
dist[0][0] = 0;
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};
while (head < tail) {
int r = queue_r[head];
int c = queue_c[head];
head++;
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;
queue_r[tail] = nr;
queue_c[tail] = nc;
tail++;
}
}
printf("shortest path to G: %d\n", dist[2][3]);
printf("cells reached: %d\n", tail);
return 0;
}shortest path to G: 5 cells reached: 10
Explanation
Breadth-first search explores positions in order of their distance from the start, using a first-in, first-out queue. When every move costs the same, the first time the search reaches the goal is along a shortest path. A distance table doubles as the visited set: -1 means not yet reached.
C has no built-in queue, so the program implements one as an array with a head and a tail index. Each cell enters the queue at most once, so the array of grid size is large enough. The four neighbours are tried with small row and column offsets, and walls (#) and cells outside the grid are skipped.
Explore the dry run
#include <stdio.h> #define ROWS 3#define COLS 4 int main(void) { const char *grid[ROWS] = {"S.#.", "..#.", "...G"}; int dist[ROWS][COLS]; for (int r = 0; r < ROWS; r++) { for (int c = 0; c < COLS; c++) { dist[r][c] = -1; } } int queue_r[ROWS * COLS], queue_c[ROWS * COLS]; int head = 0, tail = 0; queue_r[tail] = 0; queue_c[tail] = 0; tail++; dist[0][0] = 0; int dr[] = {1, -1, 0, 0}; int dc[] = {0, 0, 1, -1}; while (head < tail) { int r = queue_r[head]; int c = queue_c[head]; head++; 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; queue_r[tail] = nr; queue_c[tail] = nc; tail++; } } printf("shortest path to G: %d\n", dist[2][3]); printf("cells reached: %d\n", tail); return 0;}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The start is at distance 0 and is the only cell in the queue. | queue = [(0,0)] | — | |
| Take the oldest cell. Cells nearer the start are always processed first. | queue = [(0,0)] | — | |
| A newly reached neighbour is one step farther than its parent. | distance grows by one per layer | — | |
| G is first reached after 5 moves, going around the wall in column 2. | dist[2][3] = 5 | shortest path to G: 5 | |
| tail counts every cell that entered the queue: the 12 cells minus the 2 walls. | dist[2][3] = 5 | shortest path to G: 5 cells reached: 10 |
Cost and common mistakes
O(R·C) time and space for R rows and C columns.
- Marking a cell visited only when it is removed from the queue allows duplicates and can overflow a fixed-size queue.
- Reading grid[nr][nc] before checking the bounds is out-of-bounds access, so check the bounds first.
- BFS gives the fewest moves, not the lowest cost. For weighted moves use Dijkstra's algorithm or A*.
Try it yourself
What is dist for a cell that cannot be reached?
Reveal answer and reasoning
It stays -1, which tells the program that no path exists.