2231.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2231 on 2006-05-16 at 14:11:07 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, 
							{ 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };

int w, h, anc;
int map[16][16], pnt[16][16], crt[16][16];

void enumer(int, int);
bool test(int, int);

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

	for(i = 0; i < 16; i++)
		for(j = 0; j < 16; j++) crt[i][j] = 8;
	for(t = 1; scanf("%d %d", &h, &w) != EOF && w != 0; t++) {
		scanf("%d", &n); anc = 0; 
		memset(map, 0, sizeof(map));
		for(i = 0; i < n; i++) {
			int c, r; scanf("%d %d", &r, &c);
			map[r][c] = 1;
		}
		enumer(0, 0);
		printf("Case %d: ", t);
		if(anc == 0) printf("Garden of Eden.\n");
		else printf("%d possible ancestors.\n", anc);
	}
	
	return 0;
}

void enumer(int x, int y)
{
	if(x == h) anc++;
	else if(y == w) enumer(x+1, 0);
	else {
		int i, j, o = x*w+y;
		for(i = 0; i < 8; i++) crt[(x+DIR[i][0]+h)%h][(y+DIR[i][1]+w)%w]--;
		for(i = 0; i < 2; i++) {
			bool can = true; pnt[x][y] = i;
			if(!crt[x][y] && !test(x, y)) can = false;
			for(j = 0; j < 8 && can; j++) {
				int px = (x+DIR[j][0]+h)%h, py = (y+DIR[j][1]+w)%w, po = px*w+py;
				if(po < o && !crt[px][py] && !test(px, py)) can = false;
			}
			if(can) enumer(x, y+1);
		}
		for(i = 0; i < 8; i++) crt[(x+DIR[i][0]+h)%h][(y+DIR[i][1]+w)%w]++;
	}
}
bool test(int x, int y)
{
	int i, nei = 0, r;
	for(i = 0; i < 8; i++)
		if(pnt[(x+DIR[i][0]+h)%h][(y+DIR[i][1]+w)%w]) nei++;
	if(!pnt[x][y]) r = (nei == 3);
	else r = (nei == 2 || nei == 3);
	return r == map[x][y];
}