1162. As Far from Land as Possible
題目:
給定一個只包含0 1的n*n方陣
0代表水且1代表陸地
找出所有水與陸地最短距離中的最大值
Example 1:
Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distan
ce 2.
Example 2:
Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distan
ce 4.
思路:
01 matrix的類似題
從陸地回推回去，將陸地的格子加進佇列
如果周邊4格有0，將為0的格子加入佇列並設為1代表已搜尋過
當所有佇列處理完即找到最遠的格子
要注意方陣全為1的case，會被搞到QQ
=================================
python code:
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
row, col = len(grid), len(grid[0])
res = -1
que = deque()
for r in range(row) :
for c in range(col) :
if grid[r][c] == 1 :
que.append([r, c])
if len(que) == row*col : return res # no 0 exist
while que :
for _ in range(len(que)) :
r, c = que.popleft()
if r+1 < row and grid[r+1][c] == 0 :
grid[r+1][c] = 1
que.append([r+1, c])
if c+1 < col and grid[r][c+1] == 0 :
grid[r][c+1] = 1
que.append([r, c+1])
if r-1 >= 0 and grid[r-1][c] == 0 :
grid[r-1][c] = 1
que.append([r-1, c])
if c-1 >= 0 and grid[r][c-1] == 0 :
grid[r][c-1] = 1
que.append([r, c-1])
res += 1
return res