A building has several exits. For every square, how far is the closest one?
What to build
A multi-source breadth-first search that fills in the distance from every square to its nearest exit.
Requirements
- Start the search from all the exits at once.
- Moves go up, down, left or right, and never onto a wall
#. - Print
#for walls, and -1 for open squares that cannot reach any exit.
Input
The first line has R and C. Each of the next R lines has C characters: E (exit), . or #. There is at least one exit.
Output
R lines with C values each, separated by spaces.
Constraints
1 ≤ R, C ≤ 30.
Example
Input:
3 4
E..#
.#..
...E
Output:
0 1 2 #
1 # 2 1
2 2 1 0
Why it works
With all the exits in the queue at distance 0, the search spreads in rings around all of them at once. So each square is first reached from whichever exit is closest, in one O(R × C) pass.
Examples
Example 1 · Input
3 4 E..# .#.. ...E
Expected output
0 1 2 # 1 # 2 1 2 2 1 0
Example 2 · Input
1 3 .E.
Expected output
1 0 1
Hints
Hint 1
Do not run one search per exit. Put every exit in the queue at the start, with distance 0.
Hint 2
Then run a normal breadth-first search. The first time a square is reached, it is from its nearest exit.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
char grid[30][32];
int dist[30][30];
int queue[900];
int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
int main(void) {
int R, C, head = 0, tail = 0;
scanf("%d %d", &R, &C);
for (int r = 0; r < R; r++) scanf("%31s", grid[r]);
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
dist[r][c] = -1;
if (grid[r][c] == 'E') {
dist[r][c] = 0;
queue[tail++] = r * C + c;
}
}
}
while (head < tail) {
int r = queue[head] / C, c = queue[head] % C;
head++;
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 (grid[nr][nc] == '#' || dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[r][c] + 1;
queue[tail++] = nr * C + nc;
}
}
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] == '#') printf("# ");
else printf("%d ", dist[r][c]);
}
printf("\n");
}
return 0;
}