면적이 가장 큰 전1자 행렬(텐센트 2012년 여름방학 실습생 채용 면접 2면 시험문제)

제목 1497: 면적이 가장 큰 전1자 행렬
시간 제한: 1초
메모리 제한: 128메가
특수 판제:아니오
제출: 1019
해결: 215
제목 설명:
하나의 M*N 행렬에서 모든 원소는 0과 1에 불과하다. 이 행렬에서 면적이 가장 큰 전1자 행렬을 찾아낸다. 최대란 원소 1의 개수가 가장 많은 것을 가리킨다.
입력:
입력은 여러 개의 테스트 샘플을 포함할 수 있습니다.모든 테스트 사례에 대해 입력한 첫 번째 줄은 두 개의 정수 m, n(1<=m, n<=1000)이다. 입력할 행렬의 크기를 대표한다.행렬은 모두 m줄이 있고, 줄마다 n개의 정수가 있으며, 각각 0이나 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년 여름방학 인턴 모집 면접
 
제목 링크: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(값의 마이너스 값)에 들어가면 단위 오류가 발생하지 않도록 보증합니다.
간단한 예를 들어 어떤 열의 값을 -1, 2, 3, 5, 3, 4, 4로 가정하자.
대응하는 줄 표시는 0 1 2 3 4 5 6 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
*/