Walls and Gates

You are given an m x n grid rooms initialized with these three possible values:

• -1 — A wall or an obstacle.
• 0 — A gate.
• 2147483647 (INF) — An empty room.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave the value as 2147483647.

Examples

Example 1

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: The gate at (0,2) fills the top-right area, and the gate at (3,0) fills the bottom-left area. Each empty room gets the shortest distance to any gate via BFS.

Example 2

Input: rooms = [[2147483647,-1],[0,-1]]

Output: [[1,-1],[0,-1]]

Explanation: The only gate is at (1,0). The empty room at (0,0) is 1 step away. The rooms at (0,1) and (1,1) are walls.

Example 3

Input: rooms = [[0,2147483647,2147483647],[2147483647,2147483647,2147483647],[2147483647,2147483647,0]]

Output: [[0,1,2],[1,2,1],[2,1,0]]

Explanation: Two gates at opposite corners. Each room gets filled with the distance to the closer gate.

Constraints

• m == rooms.length
• n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] is -1, 0, or 2147483647