01 矩阵

https://www.lintcode.com/problem/974/?utm_source=sc-cheatsheet-cyc

描述

给定一个由0和1组成的矩阵，求每个单元格最近的0的距离。 两个相邻细胞之间的距离是1。

给定矩阵的元素数不超过10,000。 在给定的矩阵中至少有一个0。 单元格在四个方向上相邻:上，下，左和右。

样例

例1:

输入:[[0,0,0], [0,0,0], [0,0,0], [0,0,0], [0,0,0]]输出:[[0,0,0], [0,0,0], [0,0,0], [0,0,0], [0,0,0]]

例2:

输入:[[0,1,0,1,1], [1,1,0,0,1], [0,0,0,1,0], [1,0,1,1,1], [1,0,0,0,1]]输出:[[0,1,0,1,2], [1,1,0,0,1], [0,0,0,1,0], [1,0,1,1,1], [1,0,0,0,1]]

解题思路

1. 把所有0都加入初始q， 以其为基点做bfs扩散。更新每个邻居的距离。

2. 把邻居也加入q，根据bfs特性，第一次遇到距离为最小。

3. 注意此刻方向遍历的做法

direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for dx, dy in direction:
    nx, ny = x + dx, y + dy
    if 0 <= nx < n and 0 <= ny < m:

通过以上步骤，可以有效地解决问题并生成符合要求的输出矩阵。

```python
from typing import (
    List,
)
from collections import deque
class Solution:
    """
    @param matrix: a 0-1 matrix
    @return: return a matrix
    """
    def update_matrix(self, matrix: List[List[int]]) -> List[List[int]]:
        # write your code here
        if not matrix:
            return matrix
        n, m = len(matrix), len(matrix[0])
        distance = [[float('inf')] * m for _ in range(n)]
        q = deque() #用deque，因为List做pop(0)复杂度是O(N)
        for x in range(n):
            for y in range(m):
                if matrix[x][y] == 0:
                    distance[x][y] = 0
                    q.append((x,y))
                
        direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        while q:
            x,y = q.popleft()
            for dx, dy in direction:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m:
                    if distance[nx][ny] > distance[x][y] + 1:
                      distance[nx][ny] = distance[x][y] + 1  
                      q.append((nx,ny))

        return distance
            




```