最大子矩阵和变形（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;
}
补充：软件开发 , C++ ,
