2427.cpp

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

/* This Code is Submitted by wywcgs for Problem 2427 on 2006-12-04 at 11:27:01 */
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 10;
const int S = 1 << (2*N);
const int INF = 1 << 10;
const int DIR[][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
 
int n, opt[S], bx, by, code[N][N];
int vst[S], case_no;
char map[N][N];
bool rd[N][N];
 
bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
int play(int, int, int);
int countNum(int);
int dfs(int, int, int);
 
int main()
{
	memset(vst, 0, sizeof(vst));
	for(case_no = 1; scanf("%d", &n) != EOF && n != 0; case_no++) {
		for(int i = 0; i < n; i++) scanf("%s", map[i]);
		int cn = 0; memset(code, -1, sizeof(code));
		int one = 0, zero = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(map[i][j] == '.') code[i][j] = cn++;
				else if(map[i][j] == '0') zero++;
				else one++;
		int pn = (zero == one ? 0 : 1);
		int best = play(0, pn, cn);
		printf("(%d,%d) %d\n", bx, by, best*(pn == 0 ? 1 : -1));
	}
	return 0;
}
 
int play(int st, int p, int bn)
{
	if(vst[st] == case_no) return opt[st];
	vst[st] = case_no;
	if(bn == 0) { opt[st] = countNum(0)-countNum(1); return opt[st]; }
	int r = (p == 0 ? -INF : INF);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++) {
			if(code[i][j] == -1) continue;
			int cp = code[i][j];
			if(st&(3<<(2*cp))) continue;
			map[i][j] = p+'0';
			int cr = play(st|((2|p)<<(2*cp)), 1-p, bn-1);
			if(st == 0 && ((p == 0 && r < cr) || (p == 1 && r > cr))) { bx = i; by = j; }
			if(p == 0) r >?= cr;
			else r <?= cr;
		}
	opt[st] = r;
	return opt[st];
}
int countNum(int num)
{
	memset(rd, false, sizeof(rd));
	int ck = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if(!rd[i][j] && map[i][j] == num+'0') ck >?= dfs(i, j, num);
	return ck;
}
int dfs(int x, int y, int k)
{
	if(rd[x][y]) return 0;
	rd[x][y] = true;
	int bcnt = 1;
	for(int i = 0; i < 4; i++) {
		int cx = x+DIR[i][0], cy = y+DIR[i][1];
		if(legal(cx, cy) && map[cx][cy] == '0'+k) bcnt += dfs(cx, cy, k);
	}
	return bcnt;
}