Pythonで2値行列の中から1だけで構成される最大の正方形を見つけるプログラム

0と1だけで構成された2値行列（バイナリマトリクス）が与えられたとき、その中に含まれる「1」だけで構成される最大の正方形の面積を求めることを考えます。

例えば、次のような入力が与えられたとしましょう。

この場合、出力は 16 となります。これは、行列の中央に存在する 4×4 の正方形（1がちょうど16個並んだ領域）が最大であるためです。

解法のアプローチ：動的計画法（DP）

この問題は動的計画法を使うことで効率的に解くことができます。基本的なアイデアは、各セルに対して「そのセルを右下の角とする最大の正方形の一辺の長さ」を順番に計算していくというものです。

具体的には、以下の手順で処理を進めます。

• 結果を格納する変数 res を 0 で初期化する
• 行列の最初の行と最初の列の各要素を確認し、res を最大値で更新する
• 2行目・2列目以降の各セルについて、値が 1 であれば、
  matrix[i][j] = min(matrix[i-1][j], matrix[i-1][j-1], matrix[i][j-1]) + 1 を計算する
• 各ステップで res を現在のセルの値と比較し、より大きければ更新する
• 最後に res の2乗（＝面積）を返す

なぜ「左・上・左上の3つのセルの最小値 ＋ 1」とするのでしょうか。あるセルを右下の角とする正方形を作るためには、その3方向すべてに同じ大きさ以上の正方形が存在している必要があるからです。3つのうち最も小さい値がボトルネックとなり、それに1を加えたものが新しい正方形の一辺の長さになります。

Pythonでの実装例

class Solution:
    def solve(self, matrix):
        res = 0
        for i in range(len(matrix)):
            res = max(res, matrix[i][0])
        for i in range(len(matrix[0])):
            res = max(res, matrix[0][i])

        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j] == 1:
                    matrix[i][j] = min(matrix[i - 1][j], matrix[i - 1][j - 1], matrix[i][j - 1]) + 1

                    res = max(res, matrix[i][j])

        return res * res

ob = Solution()
matrix = [
    [1, 0, 0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 1, 1],
    [0, 1, 1, 1, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 0]
]
print(ob.solve(matrix))

入力

matrix = [  
[1, 0, 0, 0, 0, 1, 1],  
[0, 0, 0, 0, 0, 1, 1],  
[0, 1, 1, 1, 1, 0, 0],  
[0, 1, 1, 1, 1, 0, 0],  
[0, 1, 1, 1, 1, 0, 0],  
[0, 1, 1, 1, 1, 0, 0] ]

出力

16