C: breadth-first search on a grid with an array queue
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
#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;
}