Find the fewest steps from S to G in a grid. Each step moves one square up, down, left or right, onto any square that is not a wall #. Print -1 if G cannot be reached.
What to build
A breadth-first search that finds the fewest steps through a maze.
Requirements
- Find the start while reading the grid.
- Give each square its distance when it enters the queue.
- Print -1 if the goal is never reached.
Input
A line with R and C (1 ≤ R, C ≤ 30), then R lines of C characters each: S (start, exactly one), G (goal, exactly one), . (open) or # (wall).
Output
The smallest number of steps, or -1.
Constraints
1 ≤ R, C ≤ 30, with exactly one S and one G.
Example
Input:
4 5
S..#.
##.#.
.....
.###G
Output:
7
Why it works
Breadth-first search reaches every square at distance d before any at distance d + 1, so the first time it reaches the goal is by a shortest route.
Examples
4 5 S..#. ##.#. ..... .###G
7
2 2 S# #G
-1
Hints
Hint 1
Find S while reading the grid. Fill a dist array with -1 and set dist at S to 0.
Hint 2
BFS with a queue of (row, column) pairs. For each square, try the 4 neighbours: inside the grid, not '#', and dist still -1.
Hint 3
When you take G out of the queue, print its dist. If the queue empties first, print -1.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
char g[30][31];
int dist[30][30];
int qr[900], qc[900];
int main(void) {
int R, C, sr = 0, sc = 0;
scanf("%d %d", &R, &C);
for (int r = 0; r < R; r++) {
scanf("%30s", g[r]);
for (int c = 0; c < C; c++) {
dist[r][c] = -1;
if (g[r][c] == 'S') {
sr = r;
sc = c;
}
}
}
int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
int head = 0, tail = 0;
qr[tail] = sr;
qc[tail] = sc;
tail++;
dist[sr][sc] = 0;
while (head < tail) {
int r = qr[head], c = qc[head];
head++;
if (g[r][c] == 'G') {
printf("%d\n", dist[r][c]);
return 0;
}
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (g[nr][nc] == '#' || dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
qr[tail] = nr;
qc[tail] = nc;
tail++;
}
}
printf("-1\n");
return 0;
}