leetcode542 01 矩阵求最短路径
通过动态规划，从四个方向进行状态转移。
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
dp=[[10000 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]==0:
dp[i][j]=0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if i-1>=0:
dp[i][j]=min(dp[i-1][j]+1,dp[i][j])
if j-1>=0:
dp[i][j]=min(dp[i][j-1]+1,dp[i][j])
for i in range(len(matrix)-1,-1,-1):
for j in range(len(matrix[0])-1,-1,-1):
if i+1<len(matrix):
dp[i][j]=min(dp[i+1][j]+1,dp[i][j])
if j+1<len(matrix[0]):
dp[i][j]=min(dp[i][j],dp[i][j+1]+1)
for i in range(len(matrix)):
for j in range(len(matrix[0])-1,-1,-1):
if i-1>=0:
dp[i][j]=min(dp[i-1][j]+1,dp[i][j])
if j+1<len(matrix[0]):
dp[i][j]=min(dp[i][j],dp[i][j+1]+1)
for i in range(len(matrix)-1,-1,-1):
for j in range(len(matrix[0])):
if i+1<len(matrix):
dp[i][j]=min(dp[i+1][j]+1,dp[i][j])
if j-1>=0:
dp[i][j]=min(dp[i][j],dp[i][j-1]+1)
return dp然后发现从两个方向遍历就可以，左下和右上，向右向下的移动，和向左向上的移动。
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
dp=[[10000 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]==0:
dp[i][j]=0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if i-1>=0:
dp[i][j]=min(dp[i-1][j]+1,dp[i][j])
if j-1>=0:
dp[i][j]=min(dp[i][j-1]+1,dp[i][j])
for i in range(len(matrix)-1,-1,-1):
for j in range(len(matrix[0])-1,-1,-1):
if i+1<len(matrix):
dp[i][j]=min(dp[i+1][j]+1,dp[i][j])
if j+1<len(matrix[0]):
dp[i][j]=min(dp[i][j],dp[i][j+1]+1)
return dp在一个图中，能从一个点出发求这种最短距离的方法很容易想到就是 BFS，BFS 的名称是广度优先遍历，即把周围这一圈搜索完成之后，再搜索下一圈，是慢慢扩大搜索范围的。
作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/01-matrix/solution/tao-lu-da-jie-mi-gao-dong-ti-mu-kao-cha-shi-yao-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
注意：
求图中的最短路径选择BFS算法
是一圈一圈的搜索，当满足条件了就把距离输出。
每次步数加1是在每一圈结束，每一圈整体会加一步
使用visit数组记录，不要用（x,y）in visit判断这样会浪费很多时间
求1到0的距离时，这种多源的题要反过来，求0到1的最短，入队0元素，求到1的最短距离。
如果将1入队，求得是与1最近的0，这里的问题也是超级源点的问题，如果矩阵中只有一个0,那么1到0的距离就要从0开始进行计算，但是现在的问题是有多个0,那么就是把多个0看作有一个超级源点链接。
见题解 https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
queue=collections.deque()
directions=[(0,1),(1,0),(-1,0),(0,-1)]
result=[[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
visit=[[0]*len(matrix[0]) for _ in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]==0:
queue.append((i,j))
visit[i][j]=1
step=0
while queue:
size=len(queue)
for i in range(size):
x,y=queue.popleft()
if matrix[x][y]==1:
result[x][y]=step
for item in directions:
if x+item[0]<len(matrix) and x+item[0]>=0 and y+item[1]<len(matrix[0]) and y+item[1]>=0 and visit[x+item[0]][y+item[1]]!=1 :
queue.append((x+item[0],y+item[1]))
visit[x+item[0]][y+item[1]]=1
else:
continue
step+=1
return result同样可以通过matrix数组本身得到结果，这样需要matrix中的1的位置替换成-1 来标识未访问节点。
也可以通过result数组result[x][y]+=1得到结果，这样的话就不用每次for循环遍历队列当前长度，来控制这次的遍历整体移动一步了。
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
queue=collections.deque()
directions=[(0,1),(1,0),(-1,0),(0,-1)]
result=[[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]==0:
queue.append((i,j))
else:
matrix[i][j]=-1
while queue:
x,y=queue.popleft()
# if matrix[x][y]==1:
# result[x][y]=step
for item in directions:
if x+item[0]<len(matrix) and x+item[0]>=0 and y+item[1]<len(matrix[0]) and y+item[1]>=0 and matrix[x+item[0]][y+item[1]]==-1 :
matrix[x+item[0]][y+item[1]]=matrix[x][y]+1
queue.append((x+item[0],y+item[1]))
return matrix
