我提供一种奇特的解法。

思路

暴力

枚举左上角坐标 $(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; //如果[p1,p2]有沼泽，那么p1=p2
					ans=max(ans,(ed-st+1)*(l2-l1+1));
				}
				else ans=max(ans,(ed-st+1)*(l2-l1+1)); //否则可以走过来，不变
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}