2238.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2238 on 2006-05-22 at 19:27:13 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, w, b, map[BN][BN], blg[BN][BN];
bool vst[BN][BN];
vector<int> pos;

bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
bool die(int, int);
bool test(int, int, int);
void set(int, bool);

int main()
{
	int i, j, k, m;

	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		int md = (n-1)/2;
		w = b = 0; memset(map, -1, sizeof(map));
		for(i = 0; i < m; i++) {
			int x, y, o; char type;
			scanf("\n%c(%d,%d)", &type, &x, &y);
			o = (type == 'W');
			bool take = false;
			x += md; y += md; map[x][y] = o;
			for(j = 0; j < 4; j++) {
				int cx = x+DIR[j][0], cy = y+DIR[j][1];
				memset(vst, false, sizeof(vst)); pos.clear();
				if(legal(cx, cy) && map[cx][cy] == 1-o && die(cx, cy)) { take = true; set(-1, true); }
			}
		}
		memset(blg, -1, sizeof(blg));
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) {
				if(map[i][j] == -1) continue;
				for(k = 0; k < 4; k++) {
					int x = i+DIR[k][0], y = j+DIR[k][1], o = map[i][j];
					memset(vst, false, sizeof(vst)); pos.clear();
					if(legal(x, y) && map[x][y] == -1 && blg[x][y] == -1) set(test(x, y, o) ? o : -2, false);
				}
			}
		printf("%d %d\n", w, b);
	}
	
	return 0;
}

bool die(int x, int y)
{
	int i, t = map[x][y];
	pos.push_back((x<<5)|y); vst[x][y] = true;
	for(i = 0; i < 4; i++) {
		int cx = x+DIR[i][0], cy = y+DIR[i][1];
		if(!legal(cx, cy) || vst[cx][cy] || map[cx][cy] == 1-t) continue;
		else if(map[cx][cy] == -1 || !die(cx, cy)) return false;
	}
	return true;
}
bool test(int x, int y, int o)
{
	int i;
	pos.push_back((x<<5)|y); vst[x][y] = true;
	for(i = 0; i < 4; i++) {
		int cx = x+DIR[i][0], cy = y+DIR[i][1];
		if(!legal(cx, cy) || vst[cx][cy] || map[cx][cy] == o) continue;
		else if(map[cx][cy] == 1-o || !test(cx, cy, o)) return false;
	}
	return true;
}
void set(int k, bool e)
{
	unsigned int i;
	for(i = 0; i < pos.size(); i++) {
		int x = pos[i]>>5, y = pos[i]&31, o = map[x][y];
		if(e) { (o == 0) ? b++ : w++; map[x][y] = k; }
		else {
			blg[x][y] = k;
			if(k != -2) (k == 1) ? b++ : w++;
		}
	}
}