stake your claim(博弈极大极小).cpp

杭电acm解题报告2001---2099.

#include<cstdio>
#include<string>
#include<cstdlib>

int n;
char game[10][10];
int s0,s1;
char whofirst;
int dir[4][2] =
{ {1,0},{-1,0},{0,1},{0,-1} };
struct node {
	int x,y,v;
};
node edge[15];
int pos,hash[60000][2];
bool evis[15];

bool vis[10][10];
int dfs(int x,int y,char who)
{
	int i,j,c;
	c = 0;
	for(i=0;i<4;i++) {
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		if(tx<0 || ty<0 || tx>=n || ty>=n) {
			continue;
		}
		if(!vis[tx][ty] && game[tx][ty] == who) {
			vis[tx][ty] = true;
			c += dfs(tx, ty, who);
		}
	}
	return c+1;
}

inline int get_max(char who)
{
	memset(vis,0,sizeof(vis));
	int i,j;
	int mmax = 0;
	for(i=0;i<n;i++) {
		for(j=0;j<n;j++) {
			if(!vis[i][j] && game[i][j] == who) {
				vis[i][j] = true;
				int t = dfs(i,j,who);
				mmax = mmax > t ? mmax : t;
			}
		}
	}
	return mmax;
}

inline int get_score(int who)
{
	int v0 = get_max('0');
	int v1 = get_max('1');
	if(who == 0) {
		return v0-v1;
	}
	else {
		return v1-v0;
	}
}

inline int get_hash()
{
	int i,hv = 0;
	for (i=0;i<pos;i++) {
		int t = game[ edge[i].x ][ edge[i].y ];
		switch(t) {
		case '0':
			t = 0;
			break;
		case '1':
			t = 1;
			break;
		default:
			t = 2;
		}
		hv = hv*3 + t;
	}
	return hv;
}

node minmax(int left, int who)
{
	node mmax, mt;
	if(left == 0) {
		mmax.v = get_score(who);
		return mmax;
	}
	mmax.v = INT_MIN;
	int i,j,k,t;
	for (k=0;k<pos;k++) {
		if(!evis[k]) {
			i = edge[k].x;
			j = edge[k].y;
			game[i][j] = who + '0';
			evis[k] = true;
			int hv = get_hash();
			if (hash[hv][1-who] == 0x7f7f7f7f) {
				mt = minmax(left-1, 1-who);
				hash[hv][1-who] = mt.v;
			}
			else {
				mt.v = hash[hv][1-who];
			}
			mt.v = - mt.v;
			evis[k] = false;
			game[i][j] = '.';
			if(mt.v > mmax.v) {
				mmax = mt;
				mmax.x = i;
				mmax.y = j;
			}
		}
	}//for i
	return mmax;
}

int main()
{
	int i,j;
	int left;
	node move;

	while (scanf("%d",&n), n) {
		memset(hash,0x7f,sizeof(hash));
		getchar();
		s0 = s1 = left = 0;
		for(i=0;i<n;i++) {
			gets(game[i]);
			for(j=0;j<n;j++) {
				if(game[i][j] == '0') {
					s0 ++;
				}
				else if(game[i][j] == '1') {
					s1 ++;
				}
				else {
					edge[left].x = i;
					edge[left].y = j;
					left ++;
				}
			}
		}
		pos = left;
		if(s0 == s1) {//s0
			whofirst = 0;
		}
		else {//s1
			whofirst = 1;
		}
		move = minmax(left, whofirst);
		printf("(%d,%d) %d\n", move.x,move.y,move.v);
	}//while
}