生成矩阵的程序，其中每个单元格都在Python中保持曼哈顿到最接近0的距离

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

所以，如果输入像

那么输出将是

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

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

• m：=矩阵的行大小，n：=矩阵的列大小

• 对于0到m范围内的y，执行

• 如果matrix [y，x]不为零，则

• 矩阵[y，x]：=无穷大

• 对于0到n范围内的x，执行

• 对于0到m范围内的y，执行

• 如果y不为零，则

• 如果x不为零，则

• matrix [y，x] =矩阵[y，x]和矩阵[y-1，x] +1的最小值

• 矩阵[y，x] =矩阵[y，x]和矩阵[y，x-1] +1的最小值

• 对于0到n范围内的x，执行

• 对于y在m-1到0的范围内，减1，

• 如果y + 1 <m，则

• 如果x + 1 <n，则

• 矩阵[y，x] =矩阵[y，x]和矩阵[y + 1，x] +1的最小值

• 矩阵[y，x] =矩阵[y，x]和矩阵[y，x + 1] +1的最小值

• 对于范围n-1到0的x，减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]]