542. 01 矩阵

Difficulty
Medium
Tags
BFS
URL
https://leetcode-cn.com/problems/01-matrix/
Star
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
notion imagenotion image
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：
notion imagenotion image
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]
提示：
  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
  • mat 中至少有一个 0

法1 BFS

思路
从已知距离的点开始扩散！
首先把每个源点 0 入队，然后从各个 0 同时开始一圈一圈的向 1 扩散（每个 1 都是被离它最近的 0 扩散到的 ），扩散的时候可以设置 int[][] dist 来记录距离（即扩散的层次）并同时标志是否访问过。对于本题是可以直接修改原数组 int[][] matrix 来记录距离和标志是否访问的，这里要注意先把 matrix 数组中 1 的位置设置成 -1 （设成Integer.MAX_VALUE啦，m * n啦，10000啦都行，只要是个无效的距离值来标志这个位置的 1 没有被访问过就行辣~）
题解
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        queue = []
        dist = [[0]*n for _ in range(m)]
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        
        # 首先将所有的 0 都入队，
        # 并且将 1 的位置的距离设置成 最大值m+n，表示该位置是未被访问
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    queue.append((i, j))
                else:
                    dist[i][j] = m+n # 这是最大距离
        
        # 每个入队的都是已经算好距离的，
        # 所以每次出队时，出队的点周围的未被方位过的距离都是刚刚出队点的距离+1
        while queue:
            cur = queue.pop(0)
            for dir_ in dirs:
                x = cur[0] + dir_[0]
                y = cur[1] + dir_[1]

                # 防止重复进入队列
                if m > x >= 0 and n > y >= 0 and dist[x][y] == m+n:
                    dist[x][y] = dist[cur[0]][cur[1]] + 1
                    queue.append((x, y))


        return dist