bfs_leetcode 1162 地图分析
将海洋到最近陆地的最长距离，转换为陆地到海洋bfs 最后那个结果的距离。
同理 01矩阵那个题也是一样，将每个元素（0，1）到最近的0的距离，看成0到1的bfs
这两个问题都是正向去思考没办法找到最小。
有时候在纸上画一画就知道将哪个作为源点***更好
以下节选自leetcode题解
你可以想象成你从每个陆地上派了很多支船去踏上伟大航道，踏遍所有的海洋。每当船到了新的海洋，就会分裂成4条新的船，向新的未知海洋前进（访问过的海洋就不去了）。如果船到达了某个未访问过的海洋，那他们是第一个到这片海洋的。很明显，这么多船最后访问到的海洋，肯定是离陆地最远的海洋。
思考：海洋区域和陆地区域，应该哪一个作为源点集？ 也许你分析出「我们需要找一个海洋区域，满足它到陆地的最小距离是最大」会把海洋区域作为源点集。我们可以考虑后续的实现，我们知道 Dijkstra 中一个 d 数组用来维护当前源点集到其他点的最短路，而对于源点集中的任意一个点 ss，d[s_x][s_y] = 0，这很好理解，源点到源点的最短路就是 0。如果我们把海洋区域作为源点集、陆地区域作为目标点集，假设 tt 是目标点集中的一个点，算法执行结束后 d[t_x][t_y] 就是海洋区域中的点到 tt 的最短距离，但是我们却不知道哪些 tt 是海洋区域的这些点的「最近陆地区域」，我们也不知道每个 ss 距离它的「最近陆地区域」的曼哈顿距离。考虑我们把陆地区域作为源点集、海洋区域作为目标点集，目标点集中的点 tt 对应的 d[t_x][t_y] 就是海洋区域 tt 对应的距离它的「最近陆地区域」的曼哈顿距离，正是我们需要的，所以应该把陆地区域作为源点集。
直接求解不通，那反着来想，如果遍历陆地，依次筛出到陆地(最近)距离为depth=1,2...的海洋格，那最后剩下的海洋格就是到陆地的最近距离最大的，depth的最后取值就是最大的最近距离。
关键是想明白，以所有陆地格子各为中心、向外一层层延展到每个海洋格子的这种操作，对于每个海洋格子一定是最近的陆地先接触到它，也就是被遍历到，一旦被遍历到它我们就令其对应的grid[p_new[0]][p_new[1]]=1，所以每层记下来的depth就是当前这层格子到陆地的最近距离，最后的depth就是最近距离的最大值。可以参考这个题解中的图
作者：yuer-flyfly
链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible/solution/di-tu-fen-xi-yan-du-bian-li-python-by-yu-w2ek/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
注意step从-1开始，
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
# dp=[[0]*len(grid[0]) for _ in range(len(grid))]
# for i in range(len(grid)):
# for j in range(len(grid[0])):
# if i-1>=0:
# dp[i][j]=max(dp[i-1][j]+1,dp[i][j])
# if j-1>=0:
# dp[i][j]=max(dp[i][j-1]+1,dp[i][j])
# for i in range(len(grid)-1,-1,-1):
# for j in range(len(grid[0])-1,-1,-1):
# if i+1<len(grid):
# dp[i][j]=max(dp[i+1][j]+1,dp[i][j])
# if j+1<len(grid[0]):
# dp[i][j]=max(dp[i][j+1]+1,dp[i][j])
# maxvalue=0
# for i in range(len(grid)):
# for j in range(len(grid[0])):
# maxvalue=max(maxvalue,dp[i][j])
# return maxvalue
queue=collections.deque()
visit=[[0]*len(grid[0]) for _ in range(len(grid))]
dist=[]
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==1:
queue.append([i,j])
visit[i][j]=1
directions=[(0,1),(1,0),(-1,0),(0,-1)]
step=-1
while queue:
size=len(queue)
for _ in range(size):
item= queue.popleft()
dx=item[0]
dy=item[1]
print([dx,dy])
for di in directions:
x=dx+di[0]
y=dy+di[1]
if 0<=x<len(grid) and 0<=y<len(grid[0]) and visit[x][y]==0:
#print([x,y])
queue.append([x,y])
visit[x][y]=1
else:
continue
#print(visit)
step+=1
if step==0:
return -1
return step使用矩阵记录长度
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
# dp=[[0]*len(grid[0]) for _ in range(len(grid))]
# for i in range(len(grid)):
# for j in range(len(grid[0])):
# if i-1>=0:
# dp[i][j]=max(dp[i-1][j]+1,dp[i][j])
# if j-1>=0:
# dp[i][j]=max(dp[i][j-1]+1,dp[i][j])
# for i in range(len(grid)-1,-1,-1):
# for j in range(len(grid[0])-1,-1,-1):
# if i+1<len(grid):
# dp[i][j]=max(dp[i+1][j]+1,dp[i][j])
# if j+1<len(grid[0]):
# dp[i][j]=max(dp[i][j+1]+1,dp[i][j])
# maxvalue=0
# for i in range(len(grid)):
# for j in range(len(grid[0])):
# maxvalue=max(maxvalue,dp[i][j])
# return maxvalue
queue=collections.deque()
visit=[[0]*len(grid[0]) for _ in range(len(grid))]
dist=[]
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==1:
queue.append([i,j])
grid[i][j]=0
else:
grid[i][j]=-1
directions=[(0,1),(1,0),(-1,0),(0,-1)]
maxvalue=-1
print(grid)
while queue:
item= queue.popleft()
dx=item[0]
dy=item[1]
print([dx,dy])
for di in directions:
x=dx+di[0]
y=dy+di[1]
if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]==-1:
#print([x,y])
queue.append([x,y])
grid[x][y]=grid[dx][dy]+1
maxvalue=max(maxvalue,grid[x][y])
else:
continue
#print(visit)
print(grid)
if maxvalue==-1:
return -1
return maxvalue动态规划做法，求各元素到海洋的最短距离。
动态规划 从左上角遍历一遍，当(i, j)为陆地时dis[i][j] = 0；当(i, j)为海洋时，dis[i][j]为上边点与左边点的dis最小值加1。
从右下角遍历一遍，当(i, j)为陆地时dis[i][j] = 0；当(i, j)为海洋时，dis[i][j]为(下边点dis加1)、(右边点的dis加1)、(dis[i][j]本身)三者的最小值。
再去求最大
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
dp=[[0]*len(grid[0]) for _ in range(len(grid))]
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==0:
dp[i][j]=float('inf')
for i in range(len(grid)):
for j in range(len(grid[0])):
if i-1>=0:
if grid[i][j]==0:
dp[i][j]=min(dp[i-1][j]+1,dp[i][j])
if j-1>=0:
if grid[i][j]==0:
dp[i][j]=min(dp[i][j-1]+1,dp[i][j])
for i in range(len(grid)-1,-1,-1):
for j in range(len(grid[0])-1,-1,-1):
if i+1<len(grid):
if grid[i][j]==0:
dp[i][j]=min(dp[i+1][j]+1,dp[i][j])
if j+1<len(grid[0]):
if grid[i][j]==0:
dp[i][j]=min(dp[i][j+1]+1,dp[i][j])
maxvalue=0
for i in range(len(grid)):
for j in range(len(grid[0])):
maxvalue=max(maxvalue,dp[i][j])
if maxvalue==0 or maxvalue==float('inf') :
return -1
return maxvalue通过遍历为0的海洋值，bfs每次求出以此为源点的到最近陆地的距离,最后比较最大值。超时
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
def find_min(i,j):
directions=[(0,1),(1,0),(-1,0),(0,-1)]
queue=collections.deque()
visit=[[0]*len(grid[0]) for _ in range(len(grid))]
queue.append([i,j])
visit[i][j]=1
step=0
while queue:
size=len(queue)
for _ in range(size):
item= queue.popleft()
dx=item[0]
dy=item[1]
for di in directions:
x=dx+di[0]
y=dy+di[1]
if 0<=x<len(grid) and 0<=y<len(grid[0]) and visit[x][y]!=1:
if grid[x][y]==1:
return step+1
queue.append([x,y])
visit[x][y]=1
else:
continue
step+=1
return -1
maxvalue=-1
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==0:
maxvalue=max(maxvalue,find_min(i,j))
return maxvalue
