事实上和1985一摸一样。

#include <cstdio>
#include <string>

/* state: 0.34s, 404kb  */

int n, a, b;
int m[1000], r[1000], l[1000];

void pm()
{
 for(int i = 0; i < b; i ++)
 {
  printf("%d ", m[i]);
 }
 printf("\n");
}

int main()
{
 //freopen("in.txt", "r", stdin);
 int i, k, j;
 scanf("%d", &n);
 for(i = 0; i < n; i ++)
 {
  memset(m, 0, sizeof(m));
  scanf("%d %d ", &a, &b);
  //pm();
  int max = 0;
  //dp(n^2......)
  for(k = 0; k < a; k ++)
  {
   for(j = 0; j < b; j ++)
   {
    char tc; scanf("%c ", &tc);
    if(tc == 'R')
     m[j] = 0;
    else
     m[j] ++;
   }
   //pm();
   for(j = 0; j < b; j ++)
   {
    l[j] = j;
    while(l[j] > 0 && m[j] <= m[l[j] - 1])
     l[j] = l[l[j] - 1];
   }

   for(j = b - 1; j >= 0; j --)
   {
    r[j] = j;
    while(r[j] < b - 1 && m[j] <= m[r[j] + 1])
     r[j] = r[r[j] + 1];
    if(max < (r[j] - l[j] + 1) * m[j])
     max = (r[j] - l[j] + 1) * m[j];
   }
  }
  printf("%d\n", max * 3);
 }
 return 0;
}

评论