2457.cpp

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

/* This Code is Submitted by wywcgs for Problem 2457 on 2007-05-03 at 13:11:24 */
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

const int N = 32, T = 11;

int whack[N][N][T], score[N][N][T];

int getScore(int, int, int, int, int);
bool legal(int x, int y, int n) { return x >= 0 && x < n && y >= 0 && y < n; }

int main()
{
	int n, d, m;
	while(scanf("%d %d %d", &n, &d, &m) != EOF && n != 0) {
		memset(whack, 0, sizeof(whack));
		memset(score, 0, sizeof(score));
		int mt = 0;
		for(int i = 0; i < m; i++) {
			int x, y, t; scanf("%d %d %d", &x, &y, &t);
			whack[x+d][y+d][t]++; mt >?= t;
		}
		n += 2*d;
		for(int t = 1; t <= mt; t++)
			for(int x = 0; x < n; x++)
				for(int y = 0; y < n; y++)
					for(int a = -d; a <= d; a++)
						for(int b = -d; b <= d; b++)
							if(a*a+b*b <= d*d && legal(x+a, y+b, n))
								score[x][y][t] >?= score[x+a][y+b][t-1]+getScore(x, y, x+a, y+b, t);
		int res = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				res >?= score[i][j][mt];
		printf("%d\n", res);
	}
	return 0;
}

int getScore(int x1, int y1, int x2, int y2, int t)
{
	if(x1 == x2 && y1 == y2) return whack[x1][y1][t];
	int dx = x2-x1, dy = y2-y1, g = abs(__gcd(dx, dy));
	dx /= g; dy /= g;
	int res = 0;
	for(int i = 0; i <= g; i++) {
		int x = x1+i*dx, y = y1+i*dy;
		res += whack[x][y][t];
	}
	return res;
}