blog/source/_posts/2020-04-16-leetcode-01-matrix.md

title	date	tags	categories
leetcode-01-matrix	2020-04-16 12:26:34		leetcode

542. 01 矩阵

题目

想了两种思路

1. 0 位置的上下左右是 1， 上下左右中有跟 1 相邻的就是 2，以此类推，从 0 的坐标开始往上下左右四个方向扩散。如果我们把同意个距离的看作是一层，可以用一个队列依次存放每一层的坐标，直至每个坐标都被计算过。

   class Solution:
       def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
           m, n = len(matrix), len(matrix[0])
           dist = [[0] * n for _ in range(m)]
           zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
           # 将所有的 0 添加进初始队列中
           q = collections.deque(zeroes_pos)
           seen = set(zeroes_pos)
   
           # 广度优先搜索
           while q:
               i, j = q.popleft()
               for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                   if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen:
                       dist[ni][nj] = dist[i][j] + 1
                       q.append((ni, nj))
                       seen.add((ni, nj))
   
           return dist
   

2. 从左上角开往右下角遍历矩阵，当前坐标的距离由左和上两个位置的值确定。遍历一遍后，再反过来从右下角开始往左上角遍历，当前坐标的距离根据右和下两个位置的值确定，比较这两次得出的值中较小的一个即为该点的距离。