/286. Shortest Distance to Nearest Zero in Grid

286. Shortest Distance to Nearest Zero in Grid

Medium

Arrays63.8% acceptance

Given a 2D integer matrix grid where each cell is either a wall (-1), a gate (0), or an empty room (2147483647), fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, leave the value as 2147483647. Walls and gates should not be updated. Return the modified grid.

Example 1

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

Output: [[2, -1, 0, 1], [1, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

Explanation: Each empty room is filled with the shortest distance to a gate. Walls and gates are unchanged.

Example 2

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

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

Explanation: The gate at (0,0) propagates distances to reachable rooms.

Constraints

1 <= len(grid) <= 100
1 <= len(grid[0]) <= 100
Each cell in grid is one of: -1 (wall), 0 (gate), 2147483647 (empty room)
There is at least one gate in the grid

Python (current runtime)

Case 1

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

Expected: [[2, 1, 0], [-1, 2, -1], [3, -1, 4]]

Case 2

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

Expected: [[0, -1], [1, 2]]

Case 3

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

Expected: [[1, 2], [0, -1]]