Graph BFS / DFS
LC #286Medium
Walls and Gates
Graph BFS / DFS
AmazonGoogleMetaProblem
Fill each empty room with the distance to its nearest gate.
graphbfsmatrix
Constraints
- ›1 ≤ m, n ≤ 250
- ›rooms[i][j] is -1, 0, or 2³¹−1
- ›Modify rooms in-place
Example
Input
rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]]Output
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]Why
INF = 2³¹-1 (empty room), -1 = wall, 0 = gate. Fill each room with distance to nearest gate