首页 > 代码库 > 洛谷P1387 最大正方形

洛谷P1387 最大正方形

 

题目描述

在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。

输入输出格式

输入格式:

 

输入文件第一行为两个整数n,m(1<=n,m<=100),接下来n行,每行m个数字,用空格隔开,0或1.

 

输出格式:

 

一个整数,最大正方形的边长

 

输入输出样例

输入样例#1:
4 40 1 1 11 1 1 00 1 1 01 1 0 1
输出样例#1:
2

 

DP可解。

然而我选择了单调栈。栈里维护当前层可以向上延伸的高度,以及延伸的长度。min(长度,高度)即为当前最大边长(如果算长度*高度,还可以求最大矩形面积)。

n^2复杂度扫完全矩阵求最大值。

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cstring> 6 #include<cmath> 7 using namespace std; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();}11     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();}12     return x*f;13 }14 const int mxn=1200;15 int st[mxn],top;16 int h[mxn];17 int mp[mxn][mxn];18 int le[mxn],re[mxn];19 int ans=0;20 int n,m;21 void read1(){//读入22     for(int i=1;i<=n;i++){23         for(int j=1;j<=m;j++){24             mp[i][j]=read();25         }26     }27     return;28 }29 int main(){30     n=read();m=read();31     int i,j;32     read1();33     for(i=1;i<=n;i++){//34         for(j=1;j<=m;j++){//35             if(mp[i][j])h[j]++;36             else h[j]=0;37         }38         top=0;39         st[0]=0;40         for(j=1;j<=m;j++){41             while(top && h[st[top]]>=h[j])top--;//单调栈维护边界 42             le[j]=st[top];//左边界 43             st[++top]=j;//入栈 44         }45         top=0;46         st[0]=m+1;47         for(j=m;j;j--){48             while(top && h[st[top]]>=h[j])top--;49             re[j]=st[top]-1;50             st[++top]=j;51         }52         for(j=1;j<=m;j++){53             ans=max(ans,min((re[j]-le[j]),h[j]));54         }55     }56     printf("%d\n",ans);57     return 0;58 }

 

洛谷P1387 最大正方形