面積最大の全1サブマトリクス(テンセント2012年夏休み実習生募集面接二面試験問題)

題目1497:面積最大の全1サブマトリックス
時間制限:1秒
メモリ制限:128メガ
特殊問題:いいえ
コミット:1019
解決:215
タイトルの説明:
1つのM*Nの行列の中で、すべての要素は0と1だけで、この行列の中から1つの面積の最大の全1サブ行列を探し出して、いわゆる最大は要素1の個数が最も多いことを指します.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力される最初の行は2つの整数m、n(1<=m、n<=1000):入力するマトリクスのサイズを表します.行列にはm行があり、各行にはn個の整数があり、それぞれ0または1であり、隣接する2つの数の間に厳密に1つのスペースで区切られている.
出力:
各テストケースに対応して、出力マトリクスの中で面積が最も大きい全1サブマトリクスの要素数.
サンプル入力:

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

サンプル出力
0
4
ソース:
テンセントの2012年の夏休みの実習生の招聘の面接の2つの試験問題
 
タイトルリンク:http://ac.jobdu.com/problem.php?pid=1497
 
構想:単調スタックの応用;O(n*m);
 
まず元行列num[],len[i][j]を前処理し,
i行目j列を底とする最大連続幅を表し、(len[][0行0列から)if(num[i][j])len[i][j]=len[i][j-1]+num[i][j];else len[i][j]=0;
例として、行列num(1行、1列から)を次のように設定します.
                                                                               0  -1  -1  -1  -1
    0 1 1 1                                                                0   0   1   2   3
1 1 1 0は対応するlen[][]マトリクスの前処理が0 1 2 3 0である.
    1 0 1 1                                                                 0   1   0   1   2
    1 1 1 1                                                                 0   1   2   3   4
 
最後の列から遍歴し、最初の行からスタックに入るたびに、後ろの数が前より大きいときにスタックに入り、スタックの上の数より大きくないときにスタックの上の要素がスタックを出て面積を計算します.
処理テクニック先入スタック0(負の数値)はセグメントエラーが発生しないことを保証する.
簡単な例を挙げると、ある列の値を-12 3 5 3 4と仮定します.
対応する行番号は0 1 2 3 4 5 7です.
まず0をスタックに押し込み、1を押し込み(2>-1のため)、2を押し込み(3>2のため)、3をポップアップし(3<=5のため)、高さ5の幅W=4-2-1と計算した.記録面積tmp=max(tmp,5*W);次に、2(3<=3のため)をポップアップし、高さ3の幅W=4-1-1として計算する.記録面積tmp=max(tmp,3*W);次に4を押し込む.そして5を押し込む.次に、5をポップアップします(....)面積を計算し、3をポップアップし、面積を計算します.次に、1をポップアップし、面積を計算します.そして6を圧入し、最後に7を圧入する.最後にデータがなくて、スタック内の要素に対して処理面積を行って、順次弾き出して、幅は最後の圧入の要素です;.各列に対して順番に操作し、
//小最適化、ansは結果を表し、ans>=j列*m行の場合breakできます.このように、細部に注意します.
 
この問題は私も以前書いたことがありますが、今更新してください.前のコードは参考になります.http://www.cnblogs.com/yuyixingkong/p/4156602.html
 
思考が重要だ!
 

#include<stdio.h>
#include<stack>
#include<algorithm>
using namespace std;
int num[1005][1005];
int len[1005][1005];
int main()
{
    int m,n;
    while(scanf("%d %d",&m,&n)!=EOF)
    {
        for(int i=1;i<=m;i++)
        {
            len[i][0]=0;
            for(int j=1;j<=n;j++)
            {
                len[0][j]=-1;
                scanf("%d",&num[i][j]);
                if(num[i][j]) len[i][j]=len[i][j-1]+num[i][j];
                else len[i][j]=0;
            }

        }
        stack<int> S;
        int ans=0,tmp;
        for(int j=n;j>0;j--)
        {
 //           S.clear();
            int W,L;
            tmp=0;
            if(ans>=j*m) break;
            S.push(0);
            for(int i=1;i<=m;i++)
            {
                if(len[i][j]>len[S.top()][j]) {S.push(i);}
                else
                {
                    while(!S.empty()&&len[i][j]<=len[S.top()][j])
                    {
                        L=S.top();
                        S.pop();
                        int p=S.top();
                        W=(i-p-1);
                        tmp=max(tmp,W*len[L][j]);

                    }
                    S.push(i);
                }
            }
            int LL;
            if(!S.empty())LL=S.top();
            while(!S.empty())
            {
                L=S.top();
                S.pop();
                int p=S.top();
                if(p) W=(LL-p);
                else {W=LL;S.pop();}
                tmp=max(tmp,W*len[L][j]);

            }
            ans=max(tmp,ans);
        }
        printf("%d
",ans);
    }
    return 0;
}
/*
4 4
0 1 1 0
1 1 1 0
0 0 1 1
1 1 1 1
*/