Python | Leetcode Python题解之第542题01矩阵

题目：

题解：

class Solution:def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:m, n = len(matrix), len(matrix[0])# 初始化动态规划的数组，所有的距离值都设置为一个很大的数dist = [[10**9] * n for _ in range(m)]# 如果 (i, j) 的元素为 0，那么距离为 0for i in range(m):for j in range(n):if matrix[i][j] == 0:dist[i][j] = 0# 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序for i in range(m):for j in range(n):if i - 1 >= 0:dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)if j - 1 >= 0:dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)# 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序for i in range(m - 1, -1, -1):for j in range(n):if i + 1 < m:dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)if j - 1 >= 0:dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)# 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序for i in range(m):for j in range(n - 1, -1, -1):if i - 1 >= 0:dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)if j + 1 < n:dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)# 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序for i in range(m - 1, -1, -1):for j in range(n - 1, -1, -1):if i + 1 < m:dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)if j + 1 < n:dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)return dist