给出一个0-1格子地图,1表示陆地,0表示水,问距离陆地最远的水的距离(曼哈顿距离)多少
先找出所有1的格子,然后BFS所有0的格子,每次把上一步所有压进队列的格子全部更新一遍,直到所有为0的格子走完
#1162
#Runtime: 512 ms (Beats 76.36%)
#Memory: 15.2 MB (Beats 27.27%)
class Solution(object):
def maxDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
ans = -1
n = len(grid)
d = [[-1, 0], [1, 0], [0, -1], [0, 1]]
q = deque()
vis = set()
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
q.append([i, j])
if not q or len(q) == n**2:
return -1
while q:
ans += 1
sz = len(q)
while sz:
sz -= 1
x, y = q.popleft()
for dx, dy in d:
xx = x + dx
yy = y + dy
if 0 <= xx < n and 0 <= yy < n and xx * n + yy not in vis and grid[xx][yy] == 0:
vis.add(xx * n + yy)
q.append([xx, yy])
return ans