639. Walls and Gates

MediumStackQueueBFSGrid

Given a grid of rooms where -1 is a wall, 0 is a gate, and 2147483647 is an empty room, fill each empty room with the distance to its nearest gate (leaving it as 2147483647 if unreachable). Return the updated grid. The input is JSON {rooms}.

Input: JSON {rooms}.

Output: Array — the grid with distances filled in.

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: Distances from the nearest gate.
Example 2
Input: {"rooms":[[0]]}
Output: [[0]]
Explanation: A single gate.
Example 3
Input: {"rooms":[[-1]]}
Output: [[-1]]
Explanation: A single wall.

Constraints

Asked by

MetaGoogleAmazonBloombergMicrosoft
Solve this problem in the editor →