HDu 1505 1506の補強版
1697 ワード
1506の考え方と一致する
1506
ACコード:
1506
ACコード:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define MAX 1007
using namespace std;
int t,n,m;
bool a[MAX][MAX];
int h[MAX];
int lef[MAX],rig[MAX];
int ans;
int main ( )
{
scanf ( "%d" , &t );
while ( t-- )
{
char c[10];
scanf ( "%d%d" , &n , &m );
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= m ; j++ )
{
scanf ( "%s" , c );
if ( c[0] == 'R' ) a[i][j] = 0;
else a[i][j] = 1;
}
/* for ( int i = 1 ; i <= n ; i++ )
{
for ( int j = 1 ; j <= n ; j++ )
cout << a[i][j] << " ";
cout << endl;
}*/
ans = 0;
memset ( h , 0 , sizeof ( h ) );
for ( int i = 1 ; i <= n ; i++ )
{
for ( int j = 1 ; j <= m ; j++ )
{
lef[j] = rig[j] = j;
if ( a[i][j] ) h[j]++;
else h[j] = 0;
}
for ( int j = 2 ; j <= m ; j++ )
while ( lef[j] > 1 && h[lef[j]-1]>=h[j] )
lef[j] = lef[lef[j]-1];
for ( int j = m-1 ; j >= 1 ; j-- )
while ( rig[j] < m && h[rig[j]+1]>=h[j] )
rig[j] = rig[rig[j]+1];
for ( int j = 1 ; j <= m ; j++ )
ans = max ( ans , h[j]*(rig[j]-lef[j]+1) );
}
printf ( "%d
" , ans*3 );
}
}