2013年1月25日 星期五

[UVa] 10074 - Take the Land


作法:DP, O(N*M)解, 另一篇則O(N^2*M)解
http://hoyusun.blogspot.tw/2012/03/uva-10074-take-land.html

經過長久革命終於AC..

不在多說, 修到我都不知道在寫什麼了
詳細想法參考下列網址:
http://www.csie.ntnu.edu.tw/~u91029/LargestEmptyRectangle.html#a4
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;

struct data{
    int l;
    int h;
};
int main()
{
    int n, m;
    //freopen("input.txt", "r", stdin);
    while(~scanf("%d%d", &n, &m) && n){
        int Ans = 0, map[101][101] = {}, length[101][101]={};
        for(int i = 1; i <= n; i++){
            int sum = 0;
            for(int j = 1; j <= m; j++){
                scanf("%d", &map[i][j]);
                length[i][j] = map[i][j]?0:1;
                if(length[i][j])    length[i][j] = length[i-1][j]+1;
                sum = length[i][j]?sum+1:0;
                Ans = sum > Ans?sum:Ans;
            }
        }
        stack <data> Stack;
        data node, top;
        for(int i = n; i >= 1; i--){
            int L[101]={};
            for(int j = 1; j <= m; j++){
                if(Stack.size() == 0){
                    node.h = 1, node.l = j;
                    memset(L, 0, sizeof(L));
                    Stack.push(node);
                }
                node.l = j, node.h = length[i][j];
                top = Stack.top();
                if(node.h > top.h)
                    L[node.h] = j, Stack.push(node);
                else if(node.h < top.h){
                    data tmp = Stack.top();
                    while(node.h < top.h && Stack.size()){
                        tmp = Stack.top();
                        top = Stack.top();
                        int area = tmp.h*(j-tmp.l);
                        if(tmp.h != 1)
                            Ans = area > Ans ? area : Ans;
                        Stack.pop();
                        if(Stack.size())    top = Stack.top();
                    }
                    if(node.h == 0) continue;
                    if(Stack.size()){
                        node.l = tmp.l;
                        Stack.push(node);
                    }
                }
            }
            while(Stack.size()){
                data node = Stack.top();
                Stack.pop();
                if(node.h > 1){
                    int area = node.h*(m-node.l+1);
                    Ans = area > Ans ? area : Ans;
                }
            }
        }
        printf("%d\n", Ans);
    }
    return 0;
}