文章参考[2003 年集训队论文]王知昆《浅谈用极大化思想解决最大子举证问题》

枚举

适用于棋盘较大无法使用悬线法且障碍点较少的情况

通过枚举所有的极大子矩阵找出最大子矩阵

极大子矩阵：一个每条边界都不能再向外延伸的矩阵，即矩阵的每条边上均有障碍点或者与棋盘边界重合

算法思路

先枚举极大子矩阵的左边界，然后从左向右依次扫描每一个障碍点，并不断修改可行的上下边界，从而枚举出所有以这个定点为左边界的极大子矩阵。

我们先确定了左边界所在的点，然后向右扫描，在扫描到每个点的时候，我们探索当前左右边界确定时的可行上下边界。

需要注意的是，子矩阵内不得包含障碍点，这意味这在右边界的递推过程中会出现上下边界受之前扫描过的点影响。这里考虑保留上一次扫描所确定的上下边界，若有点在里面则更新边界，在外面的点直接忽略。

以上只考虑了左边界覆盖一个点的子矩阵，我们还需要枚举左边界与棋盘边界重合而右边界覆盖一个点的情况。直接按照上方方法从右往左扫描即可。

还有一种情况，是左右边界均与棋盘边界重合，我们在预处理中判断这一步：先将所有点按照纵坐标排序，然后可以得到以相邻两个点的纵坐标为上下边界，左右边界与整个棋盘的左右边界重合的矩形。

以上三种情况，可以枚举到所有的极大子矩阵。

tip:将棋盘四个顶点视作障碍点可能更加便于算法实现

悬线法

我们不再对每一个极大子矩阵一一枚举，而是通过一些预处理试图找出可能得最大子矩阵。

顾名思义，悬线法相当于在可能的地方系上一个绳子然后向下延申直到边界或障碍。然后记录每条线可以左右移动的最远距离，从而统计出最大子矩阵。

算法思路

通过枚举出所有悬线，就可以枚举出所有极大子矩阵。由于每条悬线是由其底部的点为唯一确定的，所以在 N*M 的矩形中最多由(N-1)*M 条悬线。

既然每条悬线都由其底部的点唯一确定，所以我们只需要枚举这个点对应的悬线长度和这个点能够往右扩展的最大长度就能求解。

定义 a[i][j]为矩阵中是否有障碍点，若 a[i][j] = 1 则有障碍点，反之则无障碍点

up[i][j]为点对应的悬线长度，初始化当点非障碍点时 up[i][j] = 1

up[i][j]很容易通过递推求出，当(i, j)不是障碍点时up[i][j] = up[i-1][j]+1

重点在于如何求出悬线能够左右扩展的最大长度。一条悬线往左能扩展的最大长度一定是它所包含的所有点能往左边扩展到的做大长度的最小值，往右同理，即：我们可以通过枚举悬线上每个点往左右扩展到的最大长度来求解这条线左右扩展到的最大长度

这里 l，r 代表某点所能向左右扩展的最大长度

初始化

if(a[i][j] != 1)
    l[i][j] = r[i][j] = j;

递推时，当点(i, j)和它左边的点(i, j - 1)均不为障碍点时，l[i][j] = l[i][j-1]。同理 r，这里需要注意递推时 l[i][j]需要从左往右推，即 j 从 2 到 m，r[i][j]需要从右往左推，即 j 从 m-1 到 1

给出递推部分的代码：

for(register int i=1;i<=n;++i)
	for(register int j=2;j<=m;++j)
		if(!a[i][j]&&!a[i][j-1]) l[i][j]=l[i][j-1];
for(register int i=1;i<=n;++i)
	for(register int j=m-1;j;--j)
		if(!a[i][j]&&!a[i][j+1]) r[i][j]=r[i][j+1];
for(register int i=1;i<=n;++i)
	for(register int j=1;j<=m;++j)
    	if(!a[i][j]&&!a[i-1][j]) up[i][j]=up[i-1][j]+1;

至此，我们已经预处理完了 up,l,r 三个二维数组，接下来需要求出每条悬线所能向右扩展的最大长度。

一条悬线往左能够扩展到达的最大长度一定是它包含的所有的点能够向左扩展的最大长度的最小值。我们得到状态转移方程l[i][j] = max(l[i][j], l[i-1][j]);，往右同理，即r[i][j] = min(r[i][j], r[i-1][j])。

这里给出代码：

for(register int i=1;i<=n;++i)
	for(register int j=1;j<=m;++j) {
		if(i>=2&&!a[i][j]&&!a[i-1][j]) {
			l[i][j]=max(l[i][j],l[i-1][j]);
			r[i][j]=min(r[i][j],r[i-1][j]);
        }
		ans=max(ans,up[i][j]*(r[i][j]-l[i][j]+1));
    }

给个玉蟾宫的代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#define MAXN 1005
using namespace std;
int n,m,ans=-1;
int a[MAXN][MAXN];
int l[MAXN][MAXN],r[MAXN][MAXN],up[MAXN][MAXN];
signed main() {
	scanf("%d%d",&n,&m);
	char ch;
	for(register int i=1;i<=n;++i) {
		for(register int j=1;j<=m;++j) {
			cin>>ch;
			if(ch=='R') a[i][j]=1;
			else {
				l[i][j]=r[i][j]=j;
				up[i][j]=1;
			}
		}
	}
	for(register int i=1;i<=n;++i)
		for(register int j=2;j<=m;++j)
			if(!a[i][j]&&!a[i][j-1]) l[i][j]=l[i][j-1];
	for(register int i=1;i<=n;++i)
		for(register int j=m-1;j;--j)
			if(!a[i][j]&&!a[i][j+1]) r[i][j]=r[i][j+1];
	for(register int i=1;i<=n;++i)
        for(register int j=1;j<=m;++j)
    		if(!a[i][j]&&!a[i-1][j]) up[i][j]=up[i-1][j]+1;
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j) {
			if(i>=2&&!a[i][j]&&!a[i-1][j]) {
				l[i][j]=max(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i][j],r[i-1][j]);
			}
			ans=max(ans,up[i][j]*(r[i][j]-l[i][j]+1));
		}
	printf("%d\n",ans*3);
	return 0;
}