我提供一种奇特的解法。
思路
暴力
枚举左上角坐标 $(x_1,y_1)$ 和右上角坐标 $(x_2,y_2)$ ，然后用二维前缀和判断一下有没有沼泽地，最后算一下面积，取最大值 就是答案。
时间复杂度 $O(n^4)$ ，很明显会超时。
暴力代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<bits/stdc++.h>
using namespace std;
int sum[1145][1145];
int query(int x1,int y1,int x2,int y2){
return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char s;
cin>>s;
sum[i][j]=-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1]+(s=='X');
}
}
int ans=0;
for(int x1=1;x1<=n;x1++){
for(int y1=1;y1<=m;y1++){
for(int x2=x1;x2<=n;x2++){
for(int y2=y1;y2<=m;y2++){
if(x1==x2&&y1==y2||query(x1,y1,x2,y1)||query(x1,y1,x1,y2)||query(x2,y1,x2,y2)||query(x1,y2,x2,y2))continue;
ans=max(ans,(x2-x1+1)*(y2-y1+1));
}
}
}
}
cout<<ans<<endl;
return 0;
}
|
优化
我们可以枚举一个矩形的两列竖边 $l_1$ 和 $l_2$ ，然后枚举所有在 $[l_1,l_2]$ 间没有沼泽的横边，处理出来放到一个数组 $q$ 里，如图
我们已经保证横边没有沼泽了，我们还需要找出两条横边，且两条横边夹着的两条竖边间没有沼泽，这样就能求出矩形的面积，然后取最大值。
问题是我们要找出两条横边并且是复杂度是 $O(n)$ 的，怎么找？
定义两个指针 $p_1$ 和 $p_2$ ，遍历一下数组 $q$ ，令当前下标为 $i$ ，让 $p_2$ 等于 $i$ ，如果 $p_1$ 到 $p_2$ 间有沼泽，令 $p_1$ 等于 $p_2$ ，否则不变，计算此时的面积，取最大值。
关于这样做正确性证明：如果能走到 $[p_1,p_2-1]$ 这里，那么 $[p_1,p_2-1]$ 之间肯定是没有沼泽的，如果在 $[p_1,p_2]$ 间发现了沼泽，那么沼泽肯定是在 $[p_{2}-1,p_2]$ 之间的，也就是说区间想以 $p_2$ 结尾，开头肯定只能从 $p_2$ 开始。
时间复杂度 $O(n^3)$ 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
int sum[1145][1145],q[1145];
int query(int x1,int y1,int x2,int y2){
return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char s;
cin>>s;
sum[i][j]=-sum[i-1][j-1]+sum[i-1][j]+sum[i][j-1]+(s=='X');
}
}
int ans=0;
for(int l1=1;l1<=m;l1++){
for(int l2=l1;l2<=m;l2++){
int st,ed,p=0;
for(int l3=1;l3<=n;l3++){
if(!query(l3,l1,l3,l2))q[++p]=l3;
}
if(p==0)continue;
st=ed=q[1];
ans=max(ans,(ed-st+1)*(l2-l1+1));
for(int i=1;i<=p;i++){
ed=q[i];
if(query(st,l1,ed,l1)||query(st,l2,ed,l2)){
st=ed;
ans=max(ans,(ed-st+1)*(l2-l1+1));
}
else ans=max(ans,(ed-st+1)*(l2-l1+1));
}
}
}
cout<<ans<<endl;
return 0;
}
|
