在Python中生成矩阵，每个单元格保存距离最近的0的曼哈顿距离

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

因此，如果输入如下：

那么输出将是

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

为了解决这个问题，我们将按照以下步骤进行 –

• m：矩阵的行大小，n：矩阵的列大小
• 对于y在0到m的范围内，执行以下操作
  • 对于x在0到n的范围内，执行以下操作
    • 如果矩阵[y，x]非零，则
    • 矩阵[y，x] := 无穷大
• 对于y在0到m的范围内，执行以下操作
  • 对于x在0到n的范围内，执行以下操作
    • 如果y不为零，则
    • 矩阵[y，x] = 矩阵[y，x]和矩阵[y-1，x] + 1的最小值
    • 如果x不为零，则
    • 矩阵[y，x] = 矩阵[y，x]和矩阵[y，x-1] + 1的最小值
• 对于y在m-1到0的范围内，每次递减1，执行以下操作
  • 对于x在n-1到0的范围内，每次递减1，执行以下操作
    • 如果y + 1 < m，则
    • 矩阵[y，x] = 矩阵[y，x]和矩阵[y + 1，x] + 1的最小值
    • 如果x + 1 < n，则
    • 矩阵[y，x] = 矩阵[y，x]和矩阵[y，x + 1] + 1的最小值
• 返回矩阵

让我们看以下实现，以更好地理解 –

更多Python相关文章，请阅读：Python 教程

示例

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