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