Walls and Gates
Medium
You are given a m x n 2D grid initialized with these three possible values:
-1- A water cell that can not be traversed.0- A treasure chest.INF- A land cell that can be traversed. We use the integer2^31 - 1 = 2147483647to representINF.
Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest then the value should remain INF.
Assume the grid can only be traversed up, down, left, or right.
Modify the grid in-place.
Example 1:
Input: [ [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] ]
Example 2:
Input: [ [0,-1], [2147483647,2147483647] ] Output: [ [0,-1], [1,2] ]
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 100grid[i][j]is one of{-1, 0, 2147483647}