时间复杂度O(NM) 空间复杂度O(NM)

定义

有效竖线：

除了两个端点外，不覆盖任何一个障碍点的竖直线段。

悬线：上端覆盖了一个障碍点或者到达整个矩形上边界的有效线段。

每个悬线都与它底部的点一一对应，矩形中的每一个点（矩形顶部的点除外）都对应了一个悬线。

悬线的个数=(N-1)*M；

如果把一个极大子矩形按照横坐标的不同切割成多个与y轴平行的线段，

那么其中至少有一个悬线。

如果把一个悬线向左右两个方向尽可能的移动，

那么就得到了一个矩形，我们称它为悬线对应的矩形。

悬线对应的矩形不一定是极大子矩形，因为下边界可能还可以向下扩展。

设计算法：

原理：所有悬线对应矩形的集合一定包含了极大子矩形的集合。

通过枚举所有的悬线，找出所有的极大子矩形。

算法规模：

悬线个数＝(N－1)×M

极大子矩形个数≤悬线个数

具体方法：

设 H[i,j]为点(i,j)对应的悬线的长度。

L[i,j]为点(i,j)对应的悬线向左最多能够移动到的位置。

R[i,j]为点(i,j)对应的悬线向右最多能够移动到的位置。

！考虑点(i,j)对应的悬线与点(i-1,j)对应的悬线的关系

（递推思想）：

如果(i－1,j)为障碍点，那么，如图所示，(i,j)对应的悬线长度1，

左右能移动到的位置是整个矩形的左右边界。

即 H[i,j]＝1,

?? L[i,j]=0,R[i,j]=m

如果(i－1,j)不是障碍点，

那么，如图所示，(i,j)对应的悬线长度为(i-1,j)对应的悬线长度＋1。

即 H[i,j]＝H[i-1,j]+1

如果(i－1,j)不是障碍点，

那么，如图所示，(i,j)对应的悬线左右能移动的位置要在(i-1,j)的基础上变化。

L[i,j]=max（L[i-1,j],L[i][j]）

即(i-1,j)左边第一个障碍点的位置同理，也可以得到R[i,j]的递推式

R[i,j]=min(R[i][j],R[i-1,j]) 即(i-1,j)右边第一个障碍点的位置

P4147 玉蟾宫

洛谷链接： https://www.luogu.org/problemnew/show/P4147

My AC Code:

include

using namespace std;

const int maxn = 1005;

int map[maxn][maxn];

//map数组，0表示当前位置不能用，1表示当前位置可以用

int l[maxn][maxn],r[maxn][maxn],up[maxn][maxn];

//l[i][j],r[i][j]分别表示(i,j)坐标的点，左，右能到达的最远的点的纵坐标 也就是j

//up[i][j] 表示当前点(i,j) 距离上界的距离

//l和r数组一开始初始化为l[i][j]=r[i][j]=j; 因为 一开始最远只能到达 自己当前位置

//然后up数组一开始初始化为1，代表仅仅是当前位置的高度

int n,m,ans;

char c;

int max(int a,int b){return a>b?a:b;}

int min(int a,int b){return a>b?b:a;}

int main(){

scanf(“%d%d”,&n,&m);

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

scanf(” %c”,&c);

if(c==’F’)map[i][j]=1;

else map[i][j]=0;

l[i][j]=r[i][j]=j;

up[i][j]=1;

}

}

for(int i=1;i<=n;i++)
    for(int j=2;j<=n;j++)
        if(map[i][j]&&map[i][j-1])l[i][j]=l[i][j-1];
/*处理l数组，从左往右推*/

for(int i=1;i<=n;i++)
    for(int j=m-1;j>=1;j--)
        if(map[i][j]&&map[i][j+1])r[i][j]=r[i][j+1];
/*处理r数组，从右往左推*/

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(i>1&&map[i][j]&&map[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]);
            up[i][j]=up[i-1][j]+1;
            }
        ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);
        /*一定要r[i][j]-l[i][j]+1,不+1的话，会错误，因为这样会少计算1的距离，具体可以举例子*/
    }
}
printf("%d",3*ans);

return 0;

}

P1169 [ZJOI2007]棋盘制作

洛谷链接：https://www.luogu.org/problemnew/show/P1169

My AC Code:

/题目要求01交错,所以”!=”即可/

include

include

using namespace std;

const int maxn = 2005;

int n,m,ans,an2,x,mm[maxn][maxn];

int l[maxn][maxn],r[maxn][maxn],up[maxn][maxn];

int min(int a,int b){return a>b?b:a;}

int max(int a,int b){return a>b?a:b;}

int main(){

scanf(“%d%d”,&n,&m);

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        scanf("%d",&mm[i][j]);
        l[i][j]=r[i][j]=j;up[i][j]=1;
    }

//预处理左边界
for(int i=1;i<=n;i++)
    for(int j=2;j<=m;j++)
        if(mm[i][j]!=mm[i][j-1])l[i][j]=l[i][j-1];

//预处理右边界
for(int i=1;i<=n;i++)
    for(int j=m-1;j>=1;j--)
        if(mm[i][j+1]!=mm[i][j])r[i][j]=r[i][j+1];

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(i>1&&mm[i][j]!=mm[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]);
            up[i][j]=up[i-1][j]+1;
        }

        int x=(r[i][j]-l[i][j]+1);//横向长度
        int xx=min(x,up[i][j]);//竖向长度
        ans=max(ans,x*up[i][j]);//长方形
        an2=max(an2,xx*xx);//正方形

    }
}
printf("%d\n%d",an2,ans);
return 0;

}