1593.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1593 on 2005-12-03 at 17:20:53 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;

inline int min(int, int);

int main()
{
	char tri[MAX][2*MAX];
	int up[MAX][2*MAX], down[MAX][2*MAX], max;
	int n, t = 1;
	int i, j;

	memset(up[0], 0, sizeof(up[0]));
	memset(tri[0], 0, sizeof(tri[0]));
	while(scanf("%d\n", &n) != EOF && n != 0) {
		for(i = 1; i <= n; i++) {
			scanf("%s", tri[i]);
		}
		max = 0;
		memset(down[n+1], 0, sizeof(down[n+1]));
		memset(tri[n+1], 0, sizeof(tri[n+1]));
		for(i = 1; i <= n; i++) {
			for(j = 0; tri[i][j] != 0; j++) {
				if(j % 2 == 1 || tri[i][j] != '-') {
					up[i][j] = 0;
				} else if(tri[i-1][j+1] != '-') {
					up[i][j] = 1;
				} else {
					up[i][j] = min(up[i-1][j], up[i-1][j+2]) + 1;
				}
				if(max < up[i][j]) {
					max = up[i][j];
				}
			}
		}
		for(i = n; i >= 1; i--) {
			for(j = 0; tri[i][j] != 0; j++) {
				if(j % 2 == 0 || tri[i][j] != '-') {
					down[i][j] = 0;
				} else if(tri[i+1][j-1] != '-' || j == 1 || j == 2*(n-i)-1) {
					down[i][j] = 1;
				} else {
					down[i][j] = min(down[i+1][j], down[i+1][j-2]) + 1;
				}
				if(max < down[i][j]) {
					max = down[i][j];
				}
			}
		}
		printf("Triangle #%d\n", t++);
		printf("The largest triangle area is %d.\n\n", max*max);
	}
	
	return 0;
}

inline int min(int a, int b)
{
	return a < b ? a : b;
}