目录

1. 题目描述

2. 解题分析

3. 代码实现

1. 题目描述

给定一个由 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^4
• 1 <= m * n <= 10^4
• mat[i][j] is either 0 or 1.
• mat 中至少有一个 0 

2. 解题分析

        本题跟Leetcode1162. 地图分析(medium,BFS)有点类似。只不过1162中是找所有”1“格点距离”0“格点最近距离的最大值，而本题则是要求出所有”1“格点距离”0“格点的最近距离，并由这个距离构成一个矩阵返回。所以，代码只需要在leetcode1162的基础上略作修改调整即可。

        几个要点：

• (1) 从所有与”1“格点邻接的”0“格点开始多源并行BFS搜索
• (2) 对mat进行in-place的修改，相应地需要另外用visited来维护已访问格点
• (3) ”0“格点的距离值也是0所以不需要修改 

3. 代码实现

from typing import List
from collections import deque

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        R,C   = len(mat),len(mat[0])
        q     = deque()
        visited = set()
        for r in range(R):
            for c in range(C):
                if mat[r][c]==0:
                    for x,y in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
                        if 0<=x<R and 0<=y<C and mat[x][y]==1:
                            q.append((r,c,0))
                            break
        if len(q) == 0: return mat
        while len(q) > 0:
            r,c,layer = q.popleft()
            for x,y in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
                if 0<=x<R and 0<=y<C and mat[x][y]==1 and (x,y) not in visited:
                    visited.add((x,y))
                    q.append((x,y,layer+1))
                    mat[x][y] = layer+1
        return mat
                        
if __name__ == '__main__':
    sln = Solution()

    mat = [[1]]
    print(sln.updateMatrix(mat))  

    mat = [[0]]
    print(sln.updateMatrix(mat))  
    
    mat = mat = [[0,1],[1,0]]
    print(sln.updateMatrix(mat))  
    
    mat = mat = [[0,0,0],[0,1,0],[0,0,0]]
    print(sln.updateMatrix(mat))  

    mat = [[0,0,0],[0,1,0],[1,1,1]]
    print(sln.updateMatrix(mat))  

        执行用时：360 ms, 在所有 Python3 提交中击败了29.38%的用户

        内存消耗：17.7 MB, 在所有 Python3 提交中击败了74.13%的用户

        回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)