各セルがPythonで最も近い0からマンハッタン距離を保持する行列を生成するプログラム

バイナリ行列があるとします。同じ行列を見つける必要がありますが、各セルの値は、最も近い0までのマンハッタン距離になります。行列には少なくとも1つの0が存在すると想定できます。

したがって、入力が次のような場合

その場合、出力は次のようになります

左下のセルだけが2から最も近い0までの距離を持っているからです。

これを解決するには、次の手順に従います-

• m：=行列の行サイズ、n：=行列の列サイズ
• 0からmの範囲のyについては、
  • 0からnの範囲のxについては、
    • matrix [y、x]がゼロ以外の場合、
      • matrix [y、x]：=無限大
• 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の最小値
• m-1から0の範囲のyの場合、1ずつ減らします。
  • 範囲n-1から0のxの場合、1ずつ減らします。
    • y + 1
    • matrix [y、x] =matrix [y、x]とmatrix [y + 1、x]+1の最小値
  • x + 1
  • 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]]