给定一个NxM的01矩阵，小Hi希望从中找到一个01间隔的子方阵，并且方阵的边长越大越好。
例如对于
0100100 1000101 0101010 1010101 0101010
在右下角有一个4x4的01间隔方阵。
Input第一行包含两个整数N和M。
以下N行M列包含一个NxM的01矩阵。
对于30%的数据，1 ≤ N, M ≤ 250
对于100%的数据，1 ≤ N, M ≤ 1000
Output输出最大的01间隔方阵的边长。
Sample Input
5 7 0100100 1000101 0101010 1010101 0101010
Sample Output
4
面积DP。
加强版：hihocoder1673
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<cmath> using namespace std; const int maxn=1010; char c[maxn][maxn]; int L[maxn][maxn],H[maxn][maxn]; int a[maxn][maxn]; int main() { int n,m,i,j,ans=0; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%s",c[i]+1); for(i=1;i<=n;i++) L[i][1]=1; for(i=1;i<=m;i++) H[1][i]=1; for(i=1;i<=n;i++) for(j=2;j<=m;j++) L[i][j]=c[i][j]==c[i][j-1]?1:L[i][j-1]+1; //左延伸 for(i=1;i<=m;i++) for(j=2;j<=n;j++) H[j][i]=c[j][i]==c[j-1][i]?1:H[j-1][i]+1; //上延伸 for(i=1;i<=n;i++) for(j=1;j<=m;j++){ if(i==1||j==1||c[i][j]!=c[i-1][j-1])a[i][j]=1; //对角线是一样的 else { a[i][j]=min(a[i-1][j-1]+1,L[i][j]); a[i][j]=min(a[i][j],H[i][j]); } if(a[i][j]>ans) ans=a[i][j];//这一行复制过来的时候被删了。。。 } printf("%d ",ans); return 0; }