01 矩阵

难度: Medium

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：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 <= 10⁴
1 <= m * n <= 10⁴
mat[i][j] is either 0 or 1.
mat 中至少有一个 0

Submission

运行时间: 99 ms

内存: 18.2 MB

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        ans = [[0 for j in range(n)] for i in range(m)]
        start = []
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    start.append((i, j))

        def bfs(roots):
            visted = set()
            for root in roots:
                visted.add(root)
            to_search = roots
            level = -1
            while to_search:
                tmp = []
                level += 1
                for root in to_search:
                    x, y = root[0], root[1]
                    if mat[x][y] == 1:
                        ans[x][y] = level
                    if x - 1 >= 0 and (x-1, y) not in visted:
                        visted.add((x-1, y))
                        tmp.append((x-1, y))
                    if x + 1 < m and (x+1, y) not in visted:
                        visted.add((x+1, y))
                        tmp.append((x+1, y))
                    if y - 1 >= 0 and (x, y-1) not in visted:
                        visted.add((x, y-1))
                        tmp.append((x, y-1))
                    if y + 1 < n and (x, y+1) not in visted:
                        visted.add((x, y+1))
                        tmp.append((x, y+1))
                to_search = tmp
        bfs(start)
        return ans

Explain

该题解采用了广度优先搜索（BFS）的方法。首先，遍历整个矩阵，将所有为0的位置坐标存储到一个列表中，这些位置作为BFS的起始节点。使用一个队列来执行BFS，队列的初始内容是所有0的位置。在BFS过程中，从队列中取出位置，并将其四周的相邻位置（上、下、左、右）加入队列中，同时记录从起始节点到当前节点的距离。通过这种方式，可以确保每个元素到最近的0的距离被正确计算并存储在结果矩阵中。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])
        ans = [[0 for j in range(n)] for i in range(m)]
        start = []
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    start.append((i, j))

        def bfs(roots):
            visted = set()
            for root in roots:
                visted.add(root)
            to_search = roots
            level = -1
            while to_search:
                tmp = []
                level += 1
                for root in to_search:
                    x, y = root[0], root[1]
                    if mat[x][y] == 1:
                        ans[x][y] = level
                    if x - 1 >= 0 and (x-1, y) not in visted:
                        visted.add((x-1, y))
                        tmp.append((x-1, y))
                    if x + 1 < m and (x+1, y) not in visted:
                        visted.add((x+1, y))
                        tmp.append((x+1, y))
                    if y - 1 >= 0 and (x, y-1) not in visted:
                        visted.add((x, y-1))
                        tmp.append((x, y-1))
                    if y + 1 < n and (x, y+1) not in visted:
                        visted.add((x, y+1))
                        tmp.append((x, y+1))
                to_search = tmp
        bfs(start)
        return ans

Explore

在这个问题中，我们需要找到矩阵中每个1的位置到最近的0的距离。如果我们从每个1的位置开始进行BFS搜索0，将非常低效，因为这需要从每个1重复搜索整个矩阵。相反，如果我们从所有0的位置开始BFS，我们可以同时更新它们周围的1的最短距离。这种方法使得每个位置只被访问一次，从而显著提高效率。

为了确保不会重复访问同一个节点，算法中使用了一个名为`visited`的集合来记录已经访问过的节点。每次我们从队列中取出一个节点，我们都会检查它是否已经被访问过。如果没有被访问过，我们才会将其相邻的节点加入到队列中，并将这个节点标记为已访问。这样可以避免重复处理同一个节点，从而保证了效率和正确性。

`level`变量在算法中用来追踪从所有0的位置（起始点）到当前处理的节点的距离。在BFS中，每一层（即每一轮循环）都代表了从起点向外扩展一层，因此每处理完一层，`level`就会增加1。这样，当我们访问到一个1的位置时，其在`ans`矩阵中对应的值即为该位置到最近0的距离，也就是当前的`level`值。