首先, 题目传送门: https://www.luogu.com.cn/problem/P2701
这题其实也是一个最大正方形模板题, 只要加上一个预处理就 OK 了
预处理:
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- b[i][j]=1;
- for(int i=1;i<=t;i++){
- int x,y; cin>>x>>y;
- b[x][y]=0;
- }
然后就是模板了:
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++){
- up[i][j]=1;
- r[i][j]=l[i][j]=j;
- }
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- if(b[i][j]&&b[i][j-1]) l[i][j]=l[i][j-1];
- for(int i=1;i<=n;i++)
- for(int j=n;j>=1;j--)
- if(b[i][j]&&b[i][j+1]) r[i][j]=r[i][j+1];
- for(int i=2;i<=n;i++)
- for(int j=1;j<=n;j++){
- if(b[i][j]==b[i-1][j]==1)
- {
- up[i][j]=up[i-1][j]+1;
- l[i][j]=max(l[i][j],l[i-1][j]);
- r[i][j]=min(r[i][j],r[i-1][j]);
- }
- int s=min(up[i][j],(r[i][j]-l[i][j]+1));
- ans=max(ans,s);
- }
最后输出 ans 即可
来源: http://www.bubuko.com/infodetail-3384758.html