题目

给定一个由0和1组成的矩阵，找出每个元素到最近的0的距离。
两个相邻元素间的距离为1。

image.png

思路

最短距离——广度优先搜索bfs。

  1. class Solution:
  2.     def updateMatrix(self, matrix):
  3.         if len(matrix) == 0 or len(matrix[0]) == 0: return matrix
  4.         def bfs(ans, row, col):
  5.             # 广搜找到距离最近0的距离
  6.             step = 0
  7.             queue = [(row, col)]
  8.             while len(queue) != 0:
  9.                 for x, y in queue[:]:
  10.                     if matrix[x][y] == 0:
  11.                         ans[row][col] = step
  12.                         return
  13.                     if 0 <= x - 1 < rows:
  14.                         queue.append((x - 1, y))
  15.                     if 0 <= x + 1 < rows:
  16.                         queue.append((x + 1, y))
  17.                     if 0 <= y - 1 < cols:
  18.                         queue.append((x, y - 1))
  19.                     if 0 <= y + 1 < cols:
  20.                         queue.append((x, y + 1))
  21.                     queue.pop(0)
  22.                 step += 1
  24.         rows, cols = len(matrix), len(matrix[0])
  25.         ans = matrix.copy()
  26.         for row in range(rows):
  27.             for col in range(cols):
  28.                 if matrix[row][col] != 0:
  29.                     bfs(ans, row, col)
  30.         return ans