最大子矩陣和變形（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.2cto.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;   }