Python程序：生成矩阵，其中每个单元格的值为到最近0的曼哈顿距离

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

因此，如果输入如下所示：

那么输出将是

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

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

• m := 矩阵的行数，n := 矩阵的列数
• 对于 y 从 0 到 m：
  • 对于 x 从 0 到 n：
    • 如果 matrix[y, x] 不为零，则
      • matrix[y, x] := 无穷大
• 对于 y 从 0 到 m：
  • 对于 x 从 0 到 n：
    • 如果 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（递减）：
  • 对于 x 从 n - 1 到 0（递减）：
    • 如果 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 的最小值
• 返回矩阵

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

示例

在线演示

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))

输入

[[1, 0, 1],
[1, 0, 1],
[1, 1, 0] ]

输出

[[1, 0, 1], [1, 0, 1], [2, 1, 0]]

Arnab Chakraborty

更新于：2020年11月20日

185 次浏览

启动您的职业生涯

完成课程后获得认证

开始