2280.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2280 on 2006-08-18 at 12:30:42 */ 
#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;

const int B = 8;
const int N = B*B*B*B;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

char map[B][B+1];
int w, h, v;
int id[N], od[N], match[N], check[N];

int hash(int, int, int, int);
bool vaildP(int, int, int, int);
bool legal(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w && map[x][y] != '#'; }

class State {
private:
	int x[2], y[2];
public:
	vector<int> n;
	void ext();
	int st;
	void make(int, int, int, int);
	bool vaild() const { return vaildP(x[0], y[0], x[1], y[1]); }
};
State s[N];
void State::ext() {
	for(int i = 0; i < 4; i++)
		for(int j = 0; j < 2; j++) {
			int cx = x[j]+DIR[i][0], cy = y[j]+DIR[i][1], nk = hash(cx, cy, x[1-j], y[1-j]);
			if(legal(cx, cy) && vaildP(cx, cy, x[1-j], y[1-j])) n.push_back(nk);
		}
}
void State::make(int x1, int y1, int x2, int y2) {
	x[0] = x1; y[0] = y1; x[1] = x2; y[1] = y2;
	st = hash(x1, y1, x2, y2);
	n.clear();
}

int maxMatch(int);
bool dfs(int, int);

int main()
{
	
	while(scanf("%d %d\n", &h, &w) != EOF) {
		int x[2], y[2], sn = 0;
		for(int i = 0; i < h; i++) {
			gets(map[i]);
			for(int j = 0; j < w; j++)
				if(map[i][j] == 'P') { x[sn] = i; y[sn] = j; sn++; }
		}
		int begst = hash(x[0], y[0], x[1], y[1]), so = (x[0]+x[1]+y[0]+y[1])&1;
		memset(id, -1, sizeof(id));
		for(int i = v = 0; i < h; i++)
			for(int j = 0; j < w; j++) {
				if(map[i][j] == '#') continue;
				for(int k = i; k < h; k++)
					for(int l = 0; l < w; l++)
						if((i != k || j != l) && map[k][l] != '#') {
							int o = hash(i, j, k, l);
							if(((i+j+k+l)&1) == so && id[o] == -1) 
								{ s[o].make(i, j, k, l); id[o] = v; od[v++] = o; }
						}
			}
		for(int i = 0; i < v; i++) s[od[i]].ext();
		if(!s[begst].vaild()) { printf("Alice wins.\n"); continue; }
		int ma = maxMatch(-1), mb = maxMatch(begst);
		printf("%s wins.\n", ma == mb ? "Bob" : "Alice");
	}
	
	return 0;
}

int hash(int x1, int y1, int x2, int y2)
{
	if(x1 > x2 || (x1 == x2 && y1 > y2)) { swap(x1, x2); swap(y1, y2); }
	return (x1<<9)|(y1<<6)|(x2<<3)|y2;
}
int maxMatch(int ers)
{
	int mth = 0;
	memset(match, -1, sizeof(match)); memset(check, -1, sizeof(check));
	for(int i = 0; i < v; i++)
		if(s[od[i]].st != ers && dfs(od[i], i)) mth++;
	return mth;
}
bool dfs(int p, int k)
{
	for(int i = 0; i < s[p].n.size(); i++) {
		int np = s[p].n[i];
		if(check[np] == k) continue;
		check[np] = k;
		int t = match[np];
		match[np] = p;
		if(t == -1 || dfs(t, k)) return true;
		match[np] = t;
	}
	return false;
}
bool vaildP(int x1, int y1, int x2, int y2)
{
	if(x1 == x2 && abs(y1-y2) == 1) return false;
	else if(y1 == y2 && abs(x1-x2) == 1) return false;
	return true;
}