長方形探索： 最大長方形の面積 Largest Rectangle
2008.03.28 20:47 動的計画法
n × n のマス目のそれぞれに 1 または 0 が記してあり、その中から 1 だけから成る最大の長方形の面積を求めて下さい。
これは前に考えた正方形探索の応用で、今回は最大の長方形を探します。この問題も正方形探索で用いたアルゴリズムを応用して動的計画法で解くことができますが、正方形探索ほど単純な式では解決できません。左上角から右下角に向かって個々の要素を計算していく過程で、既に計算された左と上の要素を利用していきますが、長方形探索の場合、W[i][j] の値はそこから左上方向に向かってできる正方形の辺の長さではなく、そこから左上方向に向かってできる全ての長方形の情報を記録する必要があります。このアルゴリズムの詳しい解説が、プログラム・プロムナードに掲載されています。このアルゴリズムは、現在の要素を求めるために重複を避けながら左と上の要素をマージしたりと、プログラムがやや複雑になります。
ここでは、先に考えたヒストグラム内の最大長方形の面積を求めるアルゴリズムを応用したアルゴリズムを示します。このアルゴリズムは上記の正方形探索を応用したアルゴリズムよりもプログラムが簡単になるだけでなく、より効率の良いアルゴリズムです。アルゴリズムはいたって簡単で、まず各要素について上に向かって 1 が何個連続しているかを示すテーブル T を作ります。次に、T の各行をヒストグラムの入力と見なしヒストグラムの最大長方形の面積を求めるアルゴリズムを適用します。
001 #include<stdio.h>
002 #include<iostream>
003 #include<stack>
004 #include<algorithm>
005 #define MAX 105
006 #define BLOCK 0
007
008 using namespace std;
009
010 struct Rectangle{ int height; int pos; };
011
012 int getLargestRectangle( int size, int buffer[]){
013 stack<Rectangle> S;
014 int maxv = 0;
015 buffer[size] = 0;
016
017 for ( int i = 0; i <= size; i++ ){
018 Rectangle rect;
019 rect.height = buffer[i];
020 rect.pos = i;
021 if ( S.empty() ){
022 S.push( rect );
023 } else {
024 if ( S.top().height < rect.height ){
025 S.push( rect );
026 } else if ( S.top().height > rect.height ) {
027 int target = i;
028 while ( !S.empty() && S.top().height >= rect.height){
029 Rectangle pre = S.top(); S.pop();
030 int area = pre.height * (i - pre.pos);
031 maxv = max( maxv, area);
032 target = pre.pos;
033 }
034 rect.pos = target;
035 S.push(rect);
036 }
037 }
038 }
039 return maxv;
040 }
041
042 int size;
043 int buffer[MAX][MAX];
044 int T[MAX][MAX];
045
046 int getLargestRectangle(){
047 for ( int i = 0; i < size; i++ ){
048 for ( int j = 0; j < size; j++ ){
049 T[i][j] = 0;
050 }
051 }
052
053 for ( int j = 0; j < size; j++ ){
054 int sequence = 0;
055 for ( int i = 0; i < size; i++ ){
056 if ( buffer[i][j] == BLOCK ){
057 sequence = T[i][j] = 0;
058 } else {
059 T[i][j] = ++sequence;
060 }
061 }
062 }
063
064 int maxv = 0;
065 for ( int i = 0; i < size; i++ ){
066 maxv = max( maxv, getLargestRectangle( size, T[i] ) );
067 }
068
069 return maxv;
070 }
071
072 int main(void){
073 while( cin >> size, size ){
074 for ( int i = 0; i < size; i++ ){
075 for ( int j = 0; j < size; j++ ){
076 cin >> buffer[i][j];
077 }
078 }
079 cout << getLargestRectangle() << " ";
080 }
081
082 return 0;
083 }
n 行についてO(n)の計算量なので、これはO(n2)のアルゴリズムとなります。
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |
