542. 01 Matrix
Medium

568

76

Favorite

Share
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.
Example 1: 
Input:

0 0 0
0 1 0
0 0 0
Output:
0 0 0
0 1 0
0 0 0
Example 2: 
Input:

0 0 0
0 1 0
1 1 1
Output:
0 0 0
0 1 0
1 2 1
Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

DFS 解决是否存在xxx解的问题
BFS 解决求所有的值的问题
DP解决正推逆推的问题
这道题目，比较适合DP+BFS

递推思路

首先找到所有0点，
然后更新0点边缘的点,例如i,j i,j =min(附近的点) 

由于受到步长的限制，被更新的点总是距离最短的。

伪代码

已知点 = 零点

while True:
    更新周围1阶点，
    更新已知点
    如果 更新点的数量==所有点：
        break

from typing import List
from itertools import product
from collections import deque


class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        width = len(matrix)
        length = len(matrix[0])

        seen = set()
        queue = deque()

        def _find_near_by_points(_i, _j):
            near_by_points = []
            for direction in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                if 0 <= _i + direction[0] < width and 0 <= _j + direction[1] < length and (
                        _i + direction[0], _j + direction[1]):
                    near_by_points.append((_i + direction[0], _j + direction[1]))
            return near_by_points

        for i, j in product(range(width), range(length)):
            if matrix[i][j] == 0:
                seen.add((i, j))
                queue.append((i,j))

        while queue:
            point = queue.popleft()
            for near_by_p in _find_near_by_points(*point):
                if near_by_p not in seen:
                    matrix[near_by_p[0]][near_by_p[1]] = min([matrix[p[0]][p[1]] for
                                                              p in _find_near_by_points(*near_by_p) if
                                                              p in seen]) + 1
                    seen.add(near_by_p)
                    queue.append(near_by_p)

        return matrix