2294.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2294 on 2006-07-26 at 16:55:50 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int N = 64, L = 8;
const int DIR[][2] = { { 0, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, 0 }, { -1, 1 } };

class Tantrix {
private:
	bool check(int, int) const;
	void erase(int, int);
	bool canPos(int, int, char* str);
public:
	int n[N][N];
	bool pos[N][N];
	char *g[N][N];
	void clear();
	void insert(int, int, char*);
	void searchLegalPos();
	pii legalStep(char*);
};
bool Tantrix::check(int x, int y) const {
	if(n[x][y] != 3) return true;
	int i, side[26] = { 0 };
	for(i = 0; i < 6; i++) {
		int cx = x+DIR[i][0], cy = y+DIR[i][1];
		if(g[cx][cy] == NULL) continue;
		char c = g[cx][cy][(i+3)%6];
		side[c-'A']++;
		if(side[c-'A'] == 3) return false;
	}
	return true;
}
bool Tantrix::canPos(int x, int y, char* str) {
	int i;
	for(i = 0; i < 6; i++) {
		int cx = x+DIR[i][0], cy = y+DIR[i][1];
		if(g[cx][cy] == NULL) continue;
		if(g[cx][cy][(i+3)%6] != str[i]) return false;
	}
	return true;
}
void Tantrix::clear() {
	memset(n, 0, sizeof(n)); memset(pos, true, sizeof(pos));
	int i, j;
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			g[i][j] = NULL;
}
void Tantrix::insert(int x, int y, char* str) {
	g[x][y] = str;
	int i;
	for(i = 0; i < 6; i++) {
		int cx = x+DIR[i][0], cy = y+DIR[i][1];
		n[cx][cy]++;
	}
}
void Tantrix::erase(int x, int y) {
	g[x][y] = NULL;
	int i;
	for(i = 0; i < 6; i++) {
		int cx = x+DIR[i][0], cy = y+DIR[i][1];
		n[cx][cy]--;
	}
}
void Tantrix::searchLegalPos() {
	int i, j, k, l;
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			if(n[i][j] == 0 || g[i][j] != NULL) pos[i][j] = false;
			else if(n[i][j] == 3)
				for(k = 0; k < 6; k++)
					for(l = 1; true; l++) {
						int x = i+DIR[k][0]*l, y = j+DIR[k][1]*l;
						if(n[x][y] == 0 || g[x][y] != NULL) break;
						pos[x][y] = false;
					}
}
pii Tantrix::legalStep(char* str) {
	int i, j, k, frc = 0, lgl = 0;
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++) {
			if(!pos[i][j] || !canPos(i, j, str)) continue;
			insert(i, j, str);
			bool can = true;
			for(k = 0; k < 6 && can; k++) {
				int x = i+DIR[k][0], y = j+DIR[k][1];
				if(!check(x, y)) can = false;
			}
			erase(i, j);
			if(can) (n[i][j] == 3 ? frc : lgl)++;
		}
	return pii(frc, lgl);
}

char grid[20][L], hand[L*2];

int main()
{
	int t, T, i, j;
	Tantrix tan;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		tan.clear();
		int n; scanf("%d", &n);
		for(i = 0; i < n; i++) {
			int a, b; scanf("%d %d %s", &a, &b, grid[i]);
			tan.insert(a+N/2, b+N/2, grid[i]);
		}
		int frc = 0, lgl = 0;
		tan.searchLegalPos();
		for(i = 0; i < 5; i++) {
			scanf("%s", hand);
			strcpy(hand+7, hand+1); hand[6] = hand[0];
			for(j = 0; j < 6; j++) {
				pii p = tan.legalStep(hand+j);
				frc += p.first; lgl += p.second;
			}
		}
		printf("%d\n", frc ? frc : lgl);
	}
	
	
	return 0;
}