题解 P1681 【最大正方形II】

顾z

2018-09-03 14:31:07

Solution

题目描述-->[P1681 最大正方形II](https://www.luogu.org/problemnew/show/P1681) ## 广告: [安利blog](https://www.luogu.org/blog/RPdreamer/#) **题意概括** 给定一个01交错的矩阵,要求求出其中最大的01交错分布的正方形边长. **分析:** 一看题目,woc,悬线法裸题。 再一看,woc,这不棋盘制作。 什么?不知道**悬线法**? 那我就来bb两句. //其实是粘过来的--->自己写的[棋盘制作](https://rpdreamer.blog.luogu.org/p1169) 以下内容部分参考[@Clove_unique](https://blog.csdn.net/Clove_unique/article/details/50512624) **悬线法** 用途: 解决给定矩阵中满足条件的最大子矩阵 做法: 用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界 定义几个东西: left[i][j]:代表从(i,j)能到达的最左位置 right[i][j]:代表从(i,j)能到达的最右位置 up[i][j]:代表从(i,j)向上扩展最长长度. 这里给出递推公式: left[i][j]=max(left[i][j],left[i-1][j] right[i][j]=min(right[i][j],right[i-1][j] 至于为什么递推公式中考虑上一层的情况? 是因为up数组的定义,up数组代表**向上扩展**最长长度, 所以需要考虑上一层的情况. 然后求解正方形的情况即可。 题目要求01交错,所以"!="即可 -------------------代码--------------------- ```cpp #include<bits/stdc++.h> #define IL inline #define RI register int #define maxn 2001 IL void read(int &x){ int f=1;x=0;char s=getchar(); while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();} while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();} x*=f; } int res[maxn][maxn],left[maxn][maxn],right[maxn][maxn],up[maxn][maxn]; int n,m,ans1,ans2; int main() { read(n),read(m); for(RI i=1;i<=n;i++) for(RI j=1;j<=m;j++) { read(res[i][j]); left[i][j]=right[i][j]=j; up[i][j]=1; } for(RI i=1;i<=n;i++) for(RI j=2;j<=m;j++) if(res[i][j]!=res[i][j-1]) left[i][j]=left[i][j-1];//预处理左边界 for(RI i=1;i<=n;i++) for(RI j=m-1;j>0;j--) if(res[i][j]!=res[i][j+1]) right[i][j]=right[i][j+1];//预处理右边界 for(RI i=1;i<=n;i++) for(RI j=1;j<=m;j++) { if(i>1&&res[i][j]!=res[i-1][j]) { left[i][j]=std::max(left[i][j],left[i-1][j]); right[i][j]=std::min(right[i][j],right[i-1][j]); up[i][j]=up[i-1][j]+1; } int a=right[i][j]-left[i][j]+1; //横向长度 int b=std::min(a,up[i][j]);//竖向长度 //printf("a:%d b:%d\n",a,b); ans1=std::max(ans1,b);//正方形边长,面积就乘一下.. //ans2=std::max(ans2,a*up[i][j]);//长方形面积. } printf("%d\n",ans1); } ``` //其实悬线法题目写法都差不多... //这里面有其他悬线法题目--->[这里](https://rpdreamer.blog.luogu.org/p1169) ~~可以去试试水(逃~~