Talk is Cheap, Show Me the Code!

0%

最大全1矩阵

Posted on In

在一个n*m的矩阵中，所有的元素只有0和1。你需要从这个矩阵中找出一个面积最大的全1子矩阵（该矩阵所有元素都是1）。所谓最大是指元素1的个数最多。

输入描述:

输入的第一行是两个整数m n，表示将要输入的矩阵的大小。
矩阵共有m行，每行有n个整数，分别是0或1，相邻两数之间用一个空格隔开。

输出描述:

输出矩阵中面积最大的全1子矩阵的元素个数。

示例1
输入

4 5
1 1 1 0 0
1 1 1 0 0
1 1 0 0 0
1 1 0 0 0

输出

8

说明

n,m<=1000

zuidaquan1.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define M 2005
#define max(x,y) (x)>(y)?(x):(y)
#define S(x) sum[C][x]
using namespace std;
int sum[M][M],stk[M],L[M],R[M];
void check(int &x,int y) {
    if(x<y) x=y;
}
int solve(int C,int n) {
    int top=0;
    S(0)=-2e9,stk[++top]=0;
    for(int i=1; i<=n; i++) {
        while(S(stk[top])>=S(i)) top--;
        L[i]=stk[top];
        stk[++top]=i;
    }
    top=0;
    S(n+1)=-2e9,stk[++top]=n+1;
    for(int i=n; i>=1; i--) {
        while(S(stk[top])>=S(i)) top--;
        R[i]=stk[top];
        stk[++top]=i;
    }
    int ans=-1;
    for(int i=1; i<=n; i++) check(ans,(R[i]-L[i]-1)*S(i));
    return ans;
}
int solve() {
    int n,m;
    scanf("%d%d",&n,&m);
    memset(sum,0,sizeof(sum));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            int x;
            scanf("%d",&x);
            if(x!=0)//算出每个点向上的最大距离
                sum[i][j]=sum[i-1][j]+x;
        }
    int ans=-1;
    for(int i=1; i<=n; i++)
        check(ans,solve(i,m));
//    cerr<<n<<" "<<m<<" "<<ans<<endl;
    printf("%d\n",ans);
    return 0;
}
int main(){
    char in[20]={"zero0.in"};
    char out[20]={"zero0.out"};
    for(int cas=1;cas<=10;cas++){
        freopen(in,"r",stdin);in[4]++;
        freopen(out,"w",stdout);out[4]++;
        solve();
    }
    return 0;
}