Pythonで安全な距離を保てる最大のkの値を求めるプログラム

0と1だけで構成された2次元のバイナリ行列を考えてみましょう。ここで「0」は空きセル(誰もいないマス)、「1」は人が存在するセルを表します。2つのセル間の距離は、x座標の差とy座標の差のうち大きい方の値(チェビシェフ距離)として定義されます。ある空きセルから、行列内のすべての人、および行列の4つの辺それぞれへの距離がすべてk以上であるとき、この行列は安全係数kにおいて「安全」であるとみなされます。この記事では、安全性を保証できる最大の係数kの値を求める方法を解説します。

たとえば、入力が以下のような行列だったとしましょう。

この場合、出力は1になります。中央のセルを選べば、グリッド内のすべての人への距離が最低でも1確保できるためです。

解法の考え方

この問題は、動的計画法(DP)を使うことで効率的に解けます。基本的な発想は次のとおりです。

1. まず行列の0と1を反転(XOR 1)します。これにより「空きセル」が1に変わり、空き領域だけを扱う問題へと変換できます。
2. 反転後の行列にDPを適用し、空きセルのみで構成される「最大の正方形」の一辺の長さを求めます。
3. 最大の正方形の一辺の長さが分かれば、その中心に位置することで得られる安全距離、すなわち答えは (ans + 1) // 2 として計算できます。

アルゴリズムの手順

• N := 行列Aの行数
• M := 行列A[0]の列数
• i を 0 から N まで繰り返す:
  • j を 0 から M まで繰り返す:
    • A[i, j] := A[i, j] XOR 1(0と1を反転)
• ans := 0
• i を 0 から N まで繰り返す:
  • j を 0 から M まで繰り返す:
    • i と j がどちらも0ではなく、かつ A[i, j] が 1 の場合:
      • A[i, j] := 1 + min(A[i - 1, j], A[i, j - 1], A[i - 1, j - 1])
      • ans := max(A[i, j], ans)
• (ans + 1) // 2 を返す

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

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

まとめ

このアルゴリズムの計算量はO(N×M)で、行列を2回走査するだけで済むため非常に効率的です。0と1の反転によって「人のいない領域における最大正方形」の問題へ帰着させ、DPで一辺の長さを求め、最後に中心からの距離へ変換する、という流れがポイントです。