2133.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2133 on 2006-03-10 at 19:06:07 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int INF = 5000;

int map[MAX][MAX], best[MAX][MAX], w, h;

inline void update(int, int, int, int);

int main()
{
	int i, j, t, T;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d\n", &w, &h);
		for(i = 1; i <= h; i++) {
			char line[MAX]; gets(line);
			for(j = 1; j <= w; j++)
				switch(line[j-1]) {
				case '.': map[i][j] = 0; break;
				case '*': map[i][j] = 1; break;
				default: map[i][j] = -INF; break;
				}
		}
		int step = w + h - 2, r1, r2;
		memset(best, -1, sizeof(best)); best[1][1] = map[1][1];
		for(i = 1; i <= step; i++)
			for(r1 = min(h, i+1); r1 > 0; r1--) {
				int c1 = i - r1 + 2;
				if(c1 > w) break;
				for(r2 = min(h, i+1); r2 > r1; r2--) {
					int c2 = i - r2 + 2;
					update(r1, c1, r2, c2);
					if(c2 > w) break;
				}
				update(r1, c1, r1, c1);
			}
		printf("%d\n", best[h][h]);
	}
	
	return 0;
}

inline void update(int r1, int c1, int r2, int c2)
{
	if(c1 > w || c2 > w) { best[r1][r1] = -INF; return; }
	int i;
	for(i = 1; i < 4; i++)
		best[r1][r2] = max(best[r1][r2], best[r1-(i&1)][r2-(i>>1)]);
	best[r1][r2] += (r1 == r2) ? map[r1][c1] : (map[r1][c1]+map[r2][c2]);
}