最大子矩阵 递推 扫描线

#include<bits/stdc++.h>
#include<iostream>

using namespace std;
typedef long long ll;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
ll mod=19260817;
char cun[1005][1005];
int down[1005][1005];
int lefts[1005][1005];
int righ[1005][1005];
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        char temp;

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>cun[i][j];

            }
        }

        for(int i=1;i<=n;i++)
        {
            int ro=m+1,lo=0;
            for(int j=1;j<=m;j++)
            {
                if(cun[i][j]==‘R‘)
                {
                    down[i][j]=0;
                    lefts[i][j]=0;
                    righ[i][j]=0;
                    lo=j;
                }
                else
                {
                    down[i][j]=down[i-1][j]+1;
                    if(down[i][j]!=1)
                    lefts[i][j]=min(lefts[i-1][j],j-lo-1);
                    else
                        lefts[i][j]=j-lo-1;
                }
            }
            for(int j=m;j>=1;j--)
            {
                if(cun[i][j]==‘R‘)
                {

                    ro=j;
                }
                else
                {
                    if(down[i][j]!=1)
                    righ[i][j]=min(righ[i-1][j],ro-j-1);
                    else
                        righ[i][j]=ro-j-1;
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ans=max(ans,(righ[i][j]+lefts[i][j]+1)*down[i][j]);
            }
        }
        cout<<ans*3<<‘\n‘;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                down[i][j]=0;
                    lefts[i][j]=0;
                    righ[i][j]=0;
            }
        }
    }


}

　　Uvalive 3029    left right代表移动的极限距离 down代表能往上走的极限距离

#include<bits/stdc++.h>#include<iostream>
using namespace std;typedef long long ll;int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};ll mod=19260817;char cun[1005][1005];int down[1005][1005];int lefts[1005][1005];int righ[1005][1005];int main(){
    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    int t;    cin>>t;    while(t--)    {        int n,m;        cin>>n>>m;        char temp;
        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                cin>>cun[i][j];
            }        }
        for(int i=1;i<=n;i++)        {            int ro=m+1,lo=0;            for(int j=1;j<=m;j++)            {                if(cun[i][j]==‘R‘)                {                    down[i][j]=0;                    lefts[i][j]=0;                    righ[i][j]=0;                    lo=j;                }                else                {                    down[i][j]=down[i-1][j]+1;                    if(down[i][j]!=1)                    lefts[i][j]=min(lefts[i-1][j],j-lo-1);                    else                        lefts[i][j]=j-lo-1;                }            }            for(int j=m;j>=1;j--)            {                if(cun[i][j]==‘R‘)                {
                    ro=j;                }                else                {                    if(down[i][j]!=1)                    righ[i][j]=min(righ[i-1][j],ro-j-1);                    else                        righ[i][j]=ro-j-1;                }            }        }        int ans=0;        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                ans=max(ans,(righ[i][j]+lefts[i][j]+1)*down[i][j]);            }        }        cout<<ans*3<<‘\n‘;        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                down[i][j]=0;                    lefts[i][j]=0;                    righ[i][j]=0;            }        }    }

}

最大子矩阵 递推 扫描线

原文：https://www.cnblogs.com/donkey9/p/15240729.html