BZOJ 1057 [ZJOI2007]棋盘制作 最大子矩阵

题意:链接方法:最大子矩阵解析:这题很水- -显然最大子正方形是在最大子矩阵之中的，所以没有什么卵区别。极大子矩阵的较小边长即为极大子正方形的边长，最长边长的极大子正方形即为最大子正方形。然后呢，这题有个小小的区别，，就是他要黑白相间的？- -有什么区别呢？并没有，只需要求le,ri的时候改一下判断就OK了，非常的水。代码:;int map[N][N];int h[N][N];int le[N][N];int ri[N][N];int n,m;int main(){scanf(“%d%d”,&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf(“%d”,&map[i][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(map[i][j-1]==map[i][j])le[i][j]=1;else le[i][j]=le[i][j-1]+1;}for(int j=m;j>=1;j–){if(map[i][j+1]==map[i][j])ri[i][j]=1;else ri[i][j]=ri[i][j+1]+1;}}for(int i=2;i<=n;i++){for(int j=1;j<=m;j++){if(map[i-1][j]!=map[i][j]){h[i][j]=h[i-1][j]+1;le[i][j]=min(le[i][j],le[i-1][j]);ri[i][j]=min(ri[i][j],ri[i-1][j]);}}}int ans1=0,ans2=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int tmp=min(h[i][j]+1,le[i][j]+ri[i][j]-1);ans1=max(ans1,tmp*tmp);ans2=max(ans2,(h[i][j]+1)*(le[i][j]+ri[i][j]-1));}}printf(“%d\n%d\n”,ans1,ans2); }

版权声明：本文为博主原创文章，未经博主允许不得转载。

每一个成功者都有一个开始。勇于开始，才能找到成功的路。