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