Find the fewest moves from one corner of a grid to the other, going round the walls.
What to build
A breadth-first search on a grid of cells.
Requirements
- A
.is an open cell and a#is a wall. - Start in the top-left cell. A move goes one cell up, down, left or right, and never into a wall.
- Print the fewest moves needed to reach the bottom-right cell, or -1 if it cannot be reached.
Input
The first line has r and c. Each of the next r lines has c characters. The top-left and bottom-right cells are always open.
Output
The fewest moves, or -1.
Constraints
1 ≤ r, c ≤ 10.
Example
Input:
3 3
...
.#.
...
Output:
4
Why it works
A grid is a graph that needs no edge list, because a cell's neighbours follow from its position. Breadth-first search reaches cells in order of distance, so the first time it reaches the corner is by a shortest route.
Examples
3 3 ... .#. ...
4
2 2 .# #.
-1
Hints
Hint 1
Each open cell is a vertex, and its neighbours are the open cells above, below, left and right.
Hint 2
Keep a distance for every cell, starting at -1, and a queue of cells.
Hint 3
When a cell is first reached, its distance is one more than that of the cell it was reached from.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int r, c;
char grid[10][11];
int dist[10][10];
scanf("%d %d", &r, &c);
for (int i = 0; i < r; i++) scanf("%10s", grid[i]);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) dist[i][j] = -1;
}
int qr[100], qc[100], front = 0, rear = 0;
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
dist[0][0] = 0;
qr[rear] = 0;
qc[rear] = 0;
rear++;
while (front < rear) {
int y = qr[front], x = qc[front];
front++;
for (int d = 0; d < 4; d++) {
int ny = y + dr[d], nx = x + dc[d];
if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
if (grid[ny][nx] == '#' || dist[ny][nx] != -1) continue;
dist[ny][nx] = dist[y][x] + 1;
qr[rear] = ny;
qc[rear] = nx;
rear++;
}
}
printf("%d\n", dist[r - 1][c - 1]);
return 0;
}