题解 P1169 【[ZJOI2007]棋盘制作】
ｃｈｉｌｌ
2018-02-23 21:27:55
这道题目其实就是P2701巨大的牛棚与P4147玉蟾宫的合并。
P2701求的是可以覆盖的最大正方形，
而P4171求的则是可以覆盖的最大矩形。
首先考虑把黑白相间的棋盘转换成同一个颜色，方便之后的操作。可以通过行标与列标之和的奇偶判断是否应该染上相反的颜色。需要注意的是染完色后应该再将整个矩形都染上相反的颜色，重新进行后面的操作。
### 求最大正方形:
_f[i][j]_ 表示右下角坐标为 _(i,j)_ 的正方形的最大边长。不难发现 _f[i][j]_ 与它周围的 _f[i-1][j-1],f[i-1][j],f[i][j-1]_ 有关系。于是得出
#### f[i][j]=max{f[i-1][j-1],f[i-1][j],f[i][j-1]}+1
### 求最大矩形：（借鉴了P4147题解中XG_Zepto的思路）
建立 _l[i][j],r[i][j]_ 储存坐标 _(i,j)_ 左右最近的障碍位置
建立 _L[i][j],R[i][j]_ 储存坐标 _(i,j)_ 在矩形内左右最远可以取到的位置
建立 _H[i][j]_ 储存坐标 _(i,j)_ 所在矩形的高度
坐标 _(i,j)_ 所在矩形面积为 _h[i][j]*(R[i][j]-L[i][j]-1)
_
### 附上代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m,tmp,ans1,ans2;
int f[1001][1001],a[1001][1001],l[1001][1001],r[1001][1001],L[1001][1001],R[1001][1001],h[1001][1001];
char ch;
void work()
{
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
f[i][j]=l[i][j]=r[i][j]=L[i][j]=R[i][j]=h[i][j]=0;//初始化
for (int i=1;i<=n;i++)
{
tmp=0;
for (int j=1;j<=m;j++)//计算左边最近障碍位置
if (a[i][j]) l[i][j]=tmp;
else tmp=j,L[i][j]=0;
tmp=m+1;
for (int j=m;j>=1;j--)//计算右边最近障碍位置
if (a[i][j]) r[i][j]=tmp;
else tmp=j,R[i][j]=m+1;
}
for (int i=1;i<=m;i++) R[0][i]=m+1;//细节需留意
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j])
{
f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;//计算当前正方形边长
h[i][j]=h[i-1][j]+1;//当前矩形高度+1
L[i][j]=max(L[i-1][j],l[i][j]);//计算当前矩形最左遇到的障碍
R[i][j]=min(R[i-1][j],r[i][j]);//计算当前矩形最右遇到的障碍
ans1=max(ans1,f[i][j]*f[i][j]);//求正方形面积最大值
ans2=max(ans2,h[i][j]*(R[i][j]-L[i][j]-1));//求矩形面积最大值
}
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
cin>>a[i][j];
if ((i+j)%2!=1) a[i][j]=1-a[i][j];//在相应位置染上相反色
}
work();
for (int i=1;i<=n;i++)//重新染色
for (int j=1;j<=m;j++)
a[i][j]=1-a[i][j];
work();
cout<<ans1<<endl<<ans2<<endl;
return 0;
}
```