542. 01 Matrix 广度优先算法 二维矩阵 python

542. 01 Matrix 广度优先算法 二维矩阵 python542. 01 Matrix 广度优先算法 二维矩阵 python

题目搬运者

https://leetcode-cn.com/problems/01-matrix/
给定一个mxn的二进制矩阵,返回每个单元格最接近0的距离。
两个相邻单元格之间的距离为1。

思路 广度优先算法

  1. 从矩阵中是0的位置开始遍历周围一圈
  2. 将上一步的坐标加入队列,继续遍历周围一圈,有点类似”泛洪“操作
  3. 为了实验以上两点,需要一个队列将矩阵中是0的位置的坐标加入队列,还需要一个visit访问数组,对于被访问过的数组就不在进行操作。
  4. 因为改方法是从0开始泛洪,即周围的距离就会使最小的,不需要进行min比较最小距离。

广度优先

class Solution(object):
    def updateMatrix(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: List[List[int]]
        """
        n = len(mat)  # x
        m = len(mat[0])  # y
        que = collections.deque()
        visit = [[0] * m for _ in range(n)]
        dist = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 0:
                    que.append([i, j])
                    visit[i][j] = 1  # 该位置被入队
        # bfs
        while que:
            x, y = que.popleft()
            for mx, my in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
                if 0 <= mx < n and 0 <= my < m and visit[mx][my] == 0:
                    dist[mx][my] = dist[x][y] + 1
                    que.append((mx, my))
                    visit[mx][my] = 1

        return dist

上一篇:力扣(leecode)刷题中使用到的哈希表UThash是什么


下一篇:整体二分模板(带修)