C++で最大の正方形を見つける方法｜動的計画法による解説

問題概要

0 と 1 のみで構成された 2 次元バイナリ行列が与えられます。この中から「1」だけで構成される最大の正方形を見つけ、その面積を返してください。

たとえば、次のような行列が与えられたとしましょう。

この場合、2行目と3行目にまたがる 2×2 の正方形が存在するため、出力は 4 となります。

アルゴリズム：動的計画法

この問題は動的計画法（DP）を使うことで効率的に解けます。元の行列と同じサイズの補助行列 m を用意し、各セル m[i][j] には「位置 (i, j) を右下の角とする最大の正方形の一辺の長さ」を記録していきます。

具体的な手順は以下の通りです。

• ans := 0、n := 行数、c := 列数 とする
• n が 0 の場合は 0 を返す
• n × c のサイズの補助行列 m を作成する
• i を 0 から n−1 まで、j を 0 から c−1 まで繰り返す
  • m[i][j] := matrix[i][j]（文字 '1' / '0' を整数に変換して代入）
  • ans := max(m[i][j], ans)
• i を n−2 から 0 まで逆順に、j を 1 から c−1 まで繰り返す
  • m[i][j] が 0 でない場合、m[i][j] := 1 + min(m[i+1][j], m[i][j−1], m[i+1][j−1])
  • ans := max(ans, m[i][j])
• 最後に ans × ans を返す

なぜこの漸化式が成立するのか

あるセルが「1」のとき、そのセルを右下とする正方形の一辺の長さは、真下・左・左下の 3 つのセルの値の最小値に 1 を加えたものになります。これは、3 方向すべてが十分な長さの正方形を持っていなければ、それより大きい正方形は作れないためです。最も大きい一辺の長さを ans として追跡し、最後に 2 乗することで面積が求まります。

C++ 実装例

それでは、実際の C++ コードで確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int ans = 0;
        int n = matrix.size();
        if(!n) return 0;
        int c = matrix[0].size();
        vector<vector<int>> m(n, vector<int>(c));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < c; j++){
                m[i][j] = matrix[i][j] - '0';
                ans = max(m[i][j], ans);
            }
        }
        for(int i = n - 2; i >= 0; i--){
            for(int j = 1; j < c; j++){
                if(m[i][j]){
                    m[i][j] = 1 + min({m[i+1][j], m[i][j-1], m[i+1][j-1]});
                }
                ans = max(ans, m[i][j]);
            }
        }
        return ans * ans;
    }
};
main(){
    vector<vector<char>> v = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
    Solution ob;
    cout << ob.maximalSquare(v);
}

入力

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

出力

4

計算量

• 時間計算量：O(n × c) — 行列の全セルをそれぞれ一度ずつ処理するだけです。
• 空間計算量：O(n × c) — 元の行列と同じサイズの補助行列 m が必要です。