3120956_ac_359ms_4104k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int array[1001][1001], len[1001], left[1001], right[1001];

int main()
{
	int i, j, m, n, k;
	int tmp, ans, cas;
	char str[2];

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d%d",&n,&m);
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < m; j++)
			{
				scanf("%s",str);
				array[i][j] = (str[0]=='F');
			}
		}
		memset(len,0,sizeof(len));
		ans = 0;
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < m; j++)
			{
				if(array[i][j]==0)
					len[j] = 0;
				else
					len[j]++;
			}
			left[0] = -1;
			for(j =	1; j < m; j++)
			{
				k = j-1;
				while(k!=-1&&len[k]>=len[j])
					k = left[k];
				left[j] = k;
			}
			right[m-1] = m;
			for(j = m-2; j >= 0; j--)
			{
				k = j+1;
				while(k!=m&&len[k]>=len[j])
					k = right[k];
				right[j] = k;
			}
			for(j = 0; j < m; j++)
			{
				tmp = len[j]*(right[j]-left[j]-1);
				if(tmp > ans)
					ans = tmp;
			}
		}
		printf("%d\n",ans*3);
	}
	return 0;
}