最大正方形の面積 正方形探索

• ２重ループによって候補となる正方形の左上角(i, j)を決める


• ループによって(i,j)から右下方向にできる正方形の幅 width を決める


• ２重ループによって決められた範囲が正方形であるかチェックし、そうならば maxWidth を更新する






このアルゴリズムを実装すると以下のようになります。プログラムが５重ループになるので、O(n⁵) のアルゴリズムとなります。




001 int size;
002 char G[MAX][MAX];
003 
004 int getLargestSquareBF(){
005     int maxWidth = 0;
006     for ( int i = 0; i < size; i++ ){
007         for ( int j = 0; j < size; j++ ){
008             for ( int width = 1; width <= size - max(i, j); width++ ){
009                 bool isSquare = true;
010                 for ( int a = i; a < i + width; a++ ){
011                     for ( int b = j; b < j + width; b++ ){
012                         if ( G[a][b] == BLOCK ) {
013                             isSquare = false;
014                             break;
015                         }
016                     }
017                     if ( !isSquare ) break;
018                 }
019                 if ( isSquare ) maxWidth = max( maxWidth, width );
020                 else break;
021             }
022         }
023     }
024     return maxWidth;
025 }





このアルゴリズムは n × n のタイル上の全ての正方形を見落とすことなく調べます。しかし明らかに無駄な処理が発生します。プログラムで break しているように印がついたタイルを見つけた時点でチェックする処理を終了させ次の候補の処理に移る、というようにアルゴリズムを改善したとしても、与えられたタイルのほとんどに印が着いていない場合には上記改善も意味がなく、O(n⁵)のアルゴリズムに変わりはありません。


動的計画法による解法

この問題は動的計画法を用いればO(n²)のアルゴリズムで解くことができます。

データ
W[i][j] が (i, j) から左上に向かってできる最大の正方形の辺の長さ（タイルの数）、というような配列 W を用意します。

初期化
上端と左端のタイル（i, j が 0 の場所にあるタイル）について
T[i][j] に印が着いているならば、 W[i][j] = 0
そうでなければ、W[i][j] = 1　とします。

処理
i, j > 0 について
W[i][j] の値は、W[i-1][j-1], W[i-1][j], W[i][j-1] のうち一番小さい値に 1 を加えたものになります。例えば、下図の局面においては、左隣、左上隣、上隣の要素のうち最小の値は 2 です。これは、現在の位置を右下とした正方形の辺の長さは 2 + 1 より大きくすることはできないことを示しています。




計算が左→右、上→下の順に流れていくので、W[i][j] を計算するとき左隣、左上隣、上隣の要素の値はすでに計算済みなので、これらの解を利用することができます。このアルゴリズムを実装すると以下のようになります。プログラムが２重ループになるので、O(n²) のアルゴリズムとなります。




001 int size;
002 char G[MAX][MAX];
003 
004 int getLargestSquare(){
005     int W[MAX][MAX];
006     
007     for ( int i = 0; i < size; i++ ) {
008         W[0][i] = (G[0][i] == BLOCK) ? 0 : 1;
009         W[i][0] = (G[i][0] == BLOCK) ? 0 : 1;
010     }
011     
012     int maxWidth = 0;
013     for ( int i = 1; i < size; i++ ){
014         for ( int j = 1; j < size; j++ ){
015             if ( G[i][j] == BLOCK ) {
016                 W[i][j] = 0;
017             } else {
018                 W[i][j] = min(W[i-1][j-1], min(W[i-1][j], W[i][j-1])) + 1;
019                 maxWidth = max( maxWidth, W[i][j] );
020             }
021         }
022     }
023     
024     return maxWidth;
025 }