# 剑指 Offer II 107. 矩阵中的距离#

• 标签：广度优先搜索、数组、动态规划、矩阵
• 难度：中等

## 代码 #

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25  class Solution: def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: row_count = len(mat) col_count = len(mat[0]) dist_map = [[0 for _ in range(col_count)] for _ in range(row_count)] zeroes_pos = [] for i in range(row_count): for j in range(col_count): if mat[i][j] == 0: zeroes_pos.append((i, j)) directions = {(1, 0), (-1, 0), (0, 1), (0, -1)} queue = collections.deque(zeroes_pos) visited = set(zeroes_pos) while queue: i, j = queue.popleft() for direction in directions: new_i = i + direction[0] new_j = j + direction[1] if 0 <= new_i < row_count and 0 <= new_j < col_count and (new_i, new_j) not in visited: dist_map[new_i][new_j] = dist_map[i][j] + 1 queue.append((new_i, new_j)) visited.add((new_i, new_j)) return dist_map