Description
You are given an m x n grid rooms initialized with: -1 (wall), 0 (gate), or INF (empty room). Fill each empty room with the distance to its nearest gate. If impossible to reach a gate, leave as INF.
Examples
Input:
rooms = [[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]]Explanation:
Each room shows distance to nearest gate.
Input:
rooms = [[1]]Output:
[1]Explanation:
Minimal case with a single-element matrix.
Input:
rooms = [[2147483647,2147483647,-1],[0,2147483647,2147483647],[2147483647,-1,2147483647]]Output:
[[1,2,-1],[0,1,2],[1,-1,3]]Explanation:
This 3x3 grid has one gate at position (1,0) and walls at (0,2) and (2,1). Starting from the gate, performing BFS to find shortest distances: adjacent cells get distance 1, cells 2 steps away get distance 2, and so on. The bottom-right corner gets distance 3 as it requires going around the wall.
Constraints
- •
m == rooms.length - •
n == rooms[i].length - •
1 ≤ m, n ≤ 250