542. 01矩阵 动态规划+BFS解

题目 ：Leetcode 542. 01矩阵 一刷 （中等）

---

解题思路：

两种思路：

① 动态规划

② BFS

我一开始想到的是动态规划，这道题就好比机器人寻路那道题，下一步所得到的值，依赖于上一步的所有值的一个比较判断。

因为这道题要求上下给定的元素会在上下左右这四个方向进行判断。而机器人寻路只能向下向右走。

因此我们运用动态规划的思路就可以解题了。

法一

---

具体步骤：

① 定义元素状态：我们要求某个元素距离某1个0（题目中会出现多个0），距离要求最短。而题目中的矩阵是二维的，因此我们
就可以定义一个二维数组dp。

② 建立状态转移方程：我们这里要考虑边界的情况，上下左右四周，因此我们需要对方程分段一下。

首先考虑向右向下的情况：此时每一步的距离都会由其左和上的位置的距离比较。

但这里为了使得边界的比较容易理解一些：将状态转移分为两个比较。

if col >= 1:
    dp[row][col] = min(dp[row][col],dp[row][col-1]+1)
if row >= 1:
    dp[row][col] = min(dp[row][col],dp[row-1][col]+1)

注：

当列大于等于第二列的时候，才会考虑比较其左边。当行大于等于第二列的时候，才会考虑其上边，因为这里并没有加上边界条件，
添加边界条件最后还得删掉边界条件太麻烦了。因此就拆分成两个判断。

如果光是考虑左上的话，就有可能到这各个角落处的距离出现问题。因此还需要考虑右下。

那么此时就有可能有人问一个问题，是否还需要考虑左下和右上呢？其实我们可以仔细分析一下，
其实只要考虑左上和右下就行了，这里举个简单直观的小例子。

1
0 1 0
1

我们观察中间这个值，只需要左上和右下两次动态规划就可以满足其上下左右4中情况了。

因此右下同理。

因此状态转移公式：

① 左上：

if col >= 1:
    dp[row][col] = min(dp[row][col],dp[row][col-1]+1)
if row >= 1:
    dp[row][col] = min(dp[row][col],dp[row-1][col]+1)

② 右下：

if col < n-1:
    dp[row][col] = min(dp[row][col],dp[row][col+1]+1)
if row < m-1:
    dp[row][col] = min(dp[row][col],dp[row+1][col]+1)

③ 初始化状态为了求解最小距离，我们可以将dp数组全部赋值为float(inf)(无穷，或者大于10000的任何数)，同时找出matrix中为0的位置i,j，将dp中相应的
位置置0。如果不设置为大于10000的任何数，就有可能产生误差（会导致该位置的值不会依赖左上或右下两个方向的值来取得最小值）

④ 选取结果 结果要求返回数组，因此本题的结果可以用dp替代。

代码：

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        # 动态规划,分2部分建立状态转移方程
        # 创建二位dp数组
        m = len(matrix)
        n = len(matrix[0])
        dp = [[float(inf) for _ in range(n)] for _ in range(m)]
        for row in range(m):
            for col in range(n):
                if matrix[row][col] == 0:
                    dp[row][col] = 0
        # 向右向下
        for row in range(m):
            for col in range(n):
                if col >= 1:
                    dp[row][col] = min(dp[row][col],dp[row][col-1]+1)
                if row >= 1:
                    dp[row][col] = min(dp[row][col],dp[row-1][col]+1)
        # 向左向上
        for row in range(m-1,-1,-1):
            for col in range(n-1,-1,-1):
                if col < n-1:
                    dp[row][col] = min(dp[row][col],dp[row][col+1]+1)
                if row < m-1:
                    dp[row][col] = min(dp[row][col],dp[row+1][col]+1)

        return dp

或者直接在原矩阵上进行判断修改，这样就无须多开辟一个二维空间：

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            for j in range(n):
                max_i,max_j = 10001,10001
                if matrix[i][j] != 0:
                    if i>=1:
                        max_i = matrix[i-1][j]
                    if j>=1:
                        max_j = matrix[i][j-1]
                    matrix[i][j] = min(max_i,max_j)+1
        for i in range(m-1,-1,-1):
            for j in range(n-1,-1,-1):
                max_i,max_j = 10001,10001
				# 对不为0的值进行修改
                if matrix[i][j] != 0:
                    if i <= m-2:
                        max_i = matrix[i+1][j]
                    if j <= n-2:
                        max_j = matrix[i][j+1]
					# 因为最终要比较3个值，分别为当前位置，当前位置的下方，当前位置的右方。
                    matrix[i][j] = min(matrix[i][j], min(max_i,max_j)+1)
        return matrix

法二

DFS深度优先遍历，首先选出所有不为0的值，将这些0的位置坐标放入队列中。同时维护一个集合，用于装载
所有已经运算过一次的位置。防止多次运算重复，造成死循环。

本题中DFS的过程就是由内向外不断扩展的过程。

代码

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        from collections import deque
        m = len(matrix)
        n = len(matrix[0])
        list_zero = [(i,j) for j in range(n) for i in range(m) if matrix[i][j] == 0]
        q = deque(list_zero)
        set_ = set(list_zero)

        while(q):
            row,col = q.popleft()
            for i,j in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                if 0 <= i <= m-1 and 0 <= j <= n-1 and (i,j) not in set_ and matrix[i][j] != 0:
                    matrix[i][j] = matrix[row][col] + 1
                    set_.add((i,j))
                    q.append((i,j))
        return matrix