542.01矩阵

https://leetcode-cn.com/problems/01-matrix/

一、bfs

乍看以为是dp，后来发现要从0出发而不是直接顺序遍历矩阵

先遍历矩阵找到所有0，然后以所有0为起点bfs，0到0的距离为0，到周围第一层的距离为1，到第n层的距离为第n-1层+1，依次类推

是否会冲突？因为求最短距离，因此遵循“先到先得”原则，设置vistied矩阵标志是否访问，某个位置第二次被访问，说明已经有更近的0，跳过即可

import queue
class Solution:
    def updateMatrix(self, mat) :
        m, n = len(mat), len(mat[0])
        dist = [[0] * n for _ in range(m)]
        q = queue.Queue()
        visited = [[False] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    q.put((i, j))
                    visited[i][j] = True
        while not q.empty():
            i, j = q.get()
            # 遍历（i，j）的上下左右，如果没访问过就设置距离，并设访问标记，入队
            for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                if ni >=0 and ni < m and nj >= 0 and nj < n and not visited[ni][nj]:
                    dist[ni][nj] = dist[i][j] + 1
                    visited[ni][nj] = True
                    q.put((ni, nj))
        return dist