Pythonで安全な距離を維持できるkの最大値を見つけるプログラム

バイナリ行列があるとします。ここで、0は空のセルを意味し、1は人がいるセルを意味します。 2つのセル間の距離は、x座標の差とy座標の差の最大値です。これで、セルからマトリックス内の各人までの距離が空の正方形であり、マトリックスの各辺がすべてk以上である場合、マトリックスは係数kで安全であると見なされます。安全にできる係数kの最大値を見つける必要があります。

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

中央のセルでは、セルからグリッド内の各人までの距離が少なくとも1であるため、出力は1になります。

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

• N：=Aのサイズ

• M：=A [0]

  のサイズ

• 0からNの範囲のiの場合、実行

  • 0からMの範囲のjについては、次のようにします

    • A [i、j]：=A [i、j] XOR 1

• ans：=0

• 0からNの範囲のiの場合、実行

  • 0からMの範囲のjについては、次のようにします

    • iとjがゼロ以外で、A [i、j]が1の場合、

      • A [i、j]：=1+最小値のA[i-1、j]、A [i、j-1]およびA [i-1、j-1]

      • ans =A [i、j]とansの最大値

• return（ans + 1）/ 2

例

理解を深めるために、次の実装を見てみましょう-

class Solution:
def solve(self, A):
   N = len(A)
   M = len(A[0])
   for i in range(N):
      for j in range(M):
         A[i][j] ^= 1
   ans = 0
   for i in range(N):
      for j in range(M):
         if i and j and A[i][j]:
            A[i][j] = 1 + min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1])
            ans = max(A[i][j], ans)
   return (ans + 1) // 2
ob = Solution()
matrix = [
   [0, 0, 0, 0, 0],
   [0, 1, 1, 1, 0],
   [0, 1, 0, 1, 0],
   [0, 1, 1, 1, 0],
   [0, 0, 0, 0, 0],
]
print(ob.solve(matrix))

入力

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

出力

1