题:求二维地图上可能存在的最高点的高度。即在地图上给出水域,求对空白区域填充陆地的方法。
输入m*n的二维数组isWater,表示该位置是否为水域。1是0否。
求高度时,水域高度为0。且相邻陆地高度差最多为1。
解:
参考题解。广度优先BFS,从水域开始,填充相邻且未被设置的格子。
class Solution: def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]: m, n = len(isWater), len(isWater[0]) ans = [[water-1 for water in row] for row in isWater] #初始化,将水域高度设置为0.陆地初始化-1 q = deque((i,j) for i, row in enumerate(isWater) for j,water in enumerate(row) if water)#水域入队 while q: i, j = q.popleft() for x,y in ((i-1,j),(i+1, j), (i, j-1), (i, j+1)): if 0<=x<m and 0<=y<n and ans[x][y] == -1: ans[x][y] = ans[i][j] +1 q.append((x,y)) return ans
补充:
1.Python中比较运算可以任意串连;例如,x < y <= z
等价于 x < y and y <= z。
2.deque 双向队列,添加或弹出元素都可以是双向的。
collections --- 容器数据类型 — Python 3.10.2 文档
append(), pop()是从右端。
appendleft(), popleft()是从左端。