1644.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 40 行

/*  This Code is Submitted by wywcgs for Problem 1644 on 2006-06-08 at 16:57:36 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int SN = 1024, PRO = 3;

int main()
{
	int m, n, h[SN], l[SN];
	int t, T, i, j;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &n, &m);
		int stack[SN], top, area = 0;
		memset(h, 0, sizeof(h));
		for(i = 0; i < n; i++) {
			for(j = 0; j < m; j++) {
				char e; scanf("\n%c", &e);
				if(e == 'R') h[j] = 0;
				else h[j]++;
			}
			top = 0; stack[top++] = -1;
			for(j = 0; j < m; j++) {
				while(top != 1 && h[j] <= h[stack[top-1]]) top--;
				l[j] = stack[top-1]; stack[top++] = j;
			}
			top = 0; stack[top++] = m;
			for(j = m-1; j >= 0; j--) {
				while(top != 1 && h[j] <= h[stack[top-1]]) top--;
				area = max(area, (stack[top-1]-l[j]-1)*h[j]); stack[top++] = j;
			}
		}
		printf("%d\n", area*PRO);
	}
	
	return 0;
}