You are given a m x n 2D grid initialized with these three possible values.
-1- A wall or an obstacle.0 - A gate.INF - Infinity means an empty room.$2^{31}$ - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.Fill each empty room with the distance to its nearest gate. If it is impossible to reach a Gate, that room should remain filled with INFContact me on wechat to get Amazon、Google requent Interview questions . (wechat id : jiuzhang0607)
Example1
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]]
Explanation:
the 2D grid is:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
the answer is:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
Example2
Input:
[[0,-1],[2147483647,2147483647]]
Output:
[[0,-1],[1,2]]
題目給定了一個 m by n 整數矩陣 grid,
每個 grid[r][c] 有三種值
-1: 代表是一個牆或是阻礙物
0: 代表是一個門
INF： 這邊使用 $2^{31}$ -1 代表一個空房間