Python程式：生成矩陣，其中每個單元格的值為到最近0的曼哈頓距離

假設我們有一個二進位制矩陣。我們需要找到一個相同的矩陣，但每個單元格的值將是到最近的 0 的曼哈頓距離。我們可以假設矩陣中至少存在一個 0。

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

101
101
110

那麼輸出將是

101
101
210

因為只有左下角單元格到最近的 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]]

更新於：2020年11月20日

185 次瀏覽

啟動您的職業生涯

完成課程後獲得認證

開始
廣告