200引导我们思考O(n^3)。

O(n^3)的矩阵中的dp最经典的不就是最大子矩阵了么？

让我们回忆一下最大子矩阵是怎么搞的。

两层循环枚举起始行和终止行，预处理每一列前缀和。
一层循环做dp：
如果仅选择当前列不比选择原结果优，暂时加入原结果。
如果仅选择当前列更优，舍弃原结果，选择当前列。
实时更新ans。
然后我们发现这玩意儿和最大子矩阵差不多。

两层循环枚举起始行和中止行，预处理列的连通性。
一层循环做dp:
如果这两行中间的某一列是连通的，说明它有成为一堵纵向墙的资格。
如果随着列的枚举，这两行的连通性被破坏(之间建不成横向墙)，那么前面的纵向墙就作废。
如果一堵纵向墙前面还有另一堵未被作废的纵向墙，那么可用来更新答案。
我知道看起来云里雾里的，所以放代码吧。

for(int i=1;i<=m;i++)
{
int x=0;
for(int j=0;j<=n;j++)
if(str[j][i]=='X'||!str[j][i]) x++;
else a[j][i]=x;
}
这一段是预处理纵向连通性的。如果一数列中数字一样且非0就连通，0是沼泽。

用样例打出来的a数组是这样的：

111111
110110
012012
212212
210212
对照一下代码应该很好理解吧。

for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
for(int k=1;k<=m;k++)
枚举起始行中止行。扫过每一列。

if(str[i][k]!='.'||str[j][k]!='.') l=0;
l是较靠左的纵向墙。

如果地图中枚举出的这两行中有一片沼泽地的话，这片沼泽地的左侧的墙全都不能为这两行接下来的答案做出贡献了。所以左墙设为空。

if(a[i][k]==a[j][k]&&a[i][k])
{
if(!l) l=k;
else r=k,len=max(r-l+1,len);
}
如果满足a[i][k]==a[j][k]则纵向连通，但要排除a[i][k]==a[j][k]=0的情况（这样就是两片沼泽）。

这说明这儿有资格建纵向墙。

如果没有左侧的墙就赶紧把它设为左侧的墙。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 210
using namespace std;
int n,m,a[N][N],f[N],ans;
char str[N][N];
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",str[i]+1);
for(int i=1;i<=m;i++)
{
int x=0;
for(int j=0;j<=n;j++)
if(str[j][i]=='X'||!str[j][i]) x++;
else a[j][i]=x;
}
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{
int len=0,l=0,r=0;
memset(f,0,sizeof(f));
for(int k=1;k<=m;k++)
{
if(str[i][k]!='.'||str[j][k]!='.') l=0;
if(a[i][k]==a[j][k]&&a[i][k])
{
if(!l) l=k;
else r=k,len=max(r-l+1,len);
}
}
ans=max(ans,(j-i+1)*len);
}
printf("%d",ans);
return 0;
}

我们是从左向右枚举的，我们自然希望较靠右的墙越靠右越好，所以如果左侧墙存在，我们可以直接把这列设为右侧墙，并且答案可更新。

最后乘一乘输出就好了。