Walls and Gates
Given an m x n grid where:
- -1 = wall
- 0 = gate
- 2147483647 = empty room
Fill each empty room with the distance to its nearest gate. If impossible, leave it as 2147483647.
Output the grid, each row on a new line, values space-separated.
Example
Input
2147483647,-1,0,2147483647 2147483647,2147483647,2147483647,-1 2147483647,-1,2147483647,-1 0,-1,2147483647,2147483647
Output
3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4
Reasoning
- The algorithm starts by identifying the gates in the grid, which are the cells with a value of .
- It then performs a breadth-first search (BFS) from each gate, incrementing the distance by as it moves to adjacent empty rooms.
- During the BFS, the algorithm updates the distance of each empty room to be the minimum distance from any gate, effectively filling in the grid with the distance to the nearest gate.
- The final output is the resulting grid, where each empty room contains its distance to the nearest gate, and walls remain as .
Constraints
- 1 <= rows, cols <= 250