1004. Walls and Gates — Multi-Source BFS

Given an m x n grid 'rooms' where -1 is a wall, 0 is a gate, and 2147483647 marks an empty room, fill each empty room with the distance to its nearest gate (staying 2147483647 if no gate can reach it). Moves are 4-directional and cannot pass through walls. Return the updated grid. The input is JSON {rooms}.

Input: JSON {rooms}.

Output: Nested array — the updated grid.

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: Distances to nearest gate.

Input: {"rooms":[[0]]}
Output: [[0]]
Explanation: A gate stays 0.

Input: {"rooms":[[-1]]}
Output: [[-1]]
Explanation: A wall stays -1.

Constraints

• 1<=rows,cols<=250

Asked by