当前位置：编程学习 > C/C++ >>

最大子矩阵和变形（poj 1964 hdu 1505)


		解释详见：训练指南P50
 
[cpp]
#include <iostream>   
#include <algorithm>   
using namespace std;  
int up[1005][1005],lef[1005][1005],righ[1005][1005];  
char a[1005][1005];   
int main()  
{   www.zzzyk.com
    int t,m,n,ans,lo,ro,i,j;  
    char s;  
    cin>>t;  
    while(t--)  
    {  
        cin>>m>>n;  
        for(i=0;i<m;i++)  
        for(j=0;j<n;j++)  
            cin>>a[i][j];  
        ans=0;  
        for(i=0;i<m;i++)  
        {   lo=-1;  ro=n;  
            for(j=0;j<n;j++)   
            {  
                if(a[i][j]=='R') {lef[i][j]=up[i][j]=0; lo=j;}  
                else   
                {  
                    up[i][j]=(i==0)?1:up[i-1][j]+1;  
                    lef[i][j]=(i==0)?lo+1:max(lef[i-1][j],lo+1);  
                }  
            }  
            for(j=n-1;j>=0;j--)  
            {  
                if(a[i][j]=='R') {righ[i][j]=n; ro=j;}  
                else  righ[i][j]=(i==0)?ro-1:min(righ[i-1][j],ro-1);  
                ans=max(ans,up[i][j]*(righ[i][j]-lef[i][j]+1));  
            }  
        }  
        cout<<ans*3<<endl;  
    }  
    return 0;  
}