用 Python 编写一个生成矩阵的程序，其中每个单元格都保存与最近 0 的曼哈顿距离

pythonserver side programmingprogramming

假设我们有一个二进制矩阵。我们必须找到相同的矩阵，但每个单元格的值将是与最近 0 的曼哈顿距离。我们可以假设矩阵中至少有一个 0。

因此，如果输入如下

1	0	1
1	0	1
1	1	0

则输出将是

1	0	1
1	0	1
2	1	0

因为只有左下角单元格与最接近的 0 的距离为 2。

为了解决这个问题，我们将遵循以下步骤 −

m := 矩阵的行大小，n := 矩阵的列大小
对于 0 到 m 范围内的 y，执行
- 对于 0 到 n 范围内的 x，执行
  - 如果矩阵[y, x] 非零，则
    - matrix[y, x] := infinity
对于 0 到 m 范围内的 y，执行
- 对于 0 到 n 范围内的 x，执行
  - 如果 y 非零，则
    - matrix[y, x] = matrix[y, x] 和 matrix[y - 1, x] + 1 中的最小值
  - 如果 x 非零，则
    - matrix[y, x] = matrix[y, x] 和 matrix[y, x - 1] + 1 中的最小值
对于 y 在 m - 1 到 0 范围内，减少 1，执行
- 对于 x 在 n - 1 到 0 范围内，减少 1，执行
  - 如果 y + 1 < m，则
    - matrix[y, x] = matrix[y, x] 和 matrix[y + 1, x] + 1 中的最小值
  - 如果 x + 1 < n，则
    - matrix[y, x] = matrix[y, x] 和 matrix[y, x + 1] + 1 中的最小值
返回 matrix

让我们看看下面的实现以便更好地理解 −

示例

import math
class Solution:
   def solve(self, matrix):
      m, n = len(matrix), len(matrix[0])
      for y in range(m):
         for x in range(n):
            if matrix[y][x]:
               matrix[y][x] = math.inf
      for y in range(m):
         for x in range(n):
            if y:
               matrix[y][x] = min(matrix[y][x], matrix[y - 1][x] + 1)
            if x:
               matrix[y][x] = min(matrix[y][x], matrix[y][x - 1] + 1)
      for y in range(m - 1, -1, -1):
         for x in range(n - 1, -1, -1):
            if y + 1 < m:
               matrix[y][x] = min(matrix[y][x], matrix[y + 1][x] + 1)
            if x + 1 < n:
               matrix[y][x] = min(matrix[y][x], matrix[y][x + 1] + 1)
      return matrix
ob = Solution()
matrix = [ [1, 0, 1], [1, 0, 1], [1, 1, 0] ]
print(ob.solve(matrix))