最大子矩阵(悬挂线)

2017年07月22日 9点热度 0人点赞 0条评论

最大子矩阵(悬挂线)最大子矩阵(悬挂线)最大子矩阵(悬挂线)

//如果一个矩形最大,那么该矩形其中的一列必定可以向左向右扫描最大,时空复杂度O(n*m)
#include
#include
using namespace std;
const int mx=1002;
int a[mx][mx],l[mx][mx],up[mx][mx],r[mx][mx],n,m;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
            {
                char ch=getchar();
                while(ch!='F'&&ch!='R') ch=getchar();
                a[i][j]=ch=='F'?0:1;
            }
        int ans=0;
        for(int i=1;i<=m;++i)
        r[0][i]=m+1;
        for(int i=1; i<=n; ++i) //逐行遍历
        {
            int lo=0,ro=m+1;
            //lo记录的是该行向左最近的障碍的位置,ro向右的障碍位置
            for(int j=1; j<=m; ++j)
                if(a[i][j]) l[i][j]=up[i][j]=0,lo=j;
                else up[i][j]=up[i-1][j]+1,l[i][j]=max(l[i-1][j],lo);
            for(int j=m; j>0; --j)
                if(a[i][j]) r[i][j]=m+1,ro=j;
                else r[i][j]=min(r[i-1][j],ro),ans=max(up[i][j]*(r[i][j]-l[i][j]-1),ans);
        }
        printf("%dn",ans*3);
    }
    return 0;
}
未经允许不得转载!最大子矩阵(悬挂线)

update

纸上得来终觉浅, 绝知此事须躬行。