poj 3317 Stake Your Claim(極大極小搜尋+記憶化搜尋+狀态壓縮)

題意：給定一個n*n的矩陣（n<=8），兩個人依次向矩陣裡放0和1，玩家的得分為自己牌的數量減去對方牌的數量。

問先手的下一步最佳得分位置和得分。

設先手放0. c0為0的數量，c1為1的數量。

那麼先手得分為c0 - c1;

後手得分為c1-c0;

假設估價函數為g(x)=c0(x)-c1(x).x為某一狀态。

可以看出，先手求目前所有選擇中g(x)的最大值，後手求目前所有選擇中的最小值。

這就是博弈中的極大極小搜尋了。

直接爆搜的話會有許多的重複狀态。（每次隻是換了個地方放0或1,很容易重複）

由于空位小于等于10。考慮用三進制壓縮狀态。

0表示目前位空，1表示放0,   2表示放1.

剪枝的話，可以用alpha-beta剪枝，不過此題沒什麼效果。

#include<cstdio>
#include<cstring>
#define MAX(a,b) a>b?a:b
using namespace std;
const int INF=(1<<30);
char map[12][12];
int empty[12];int full[12];//空位
int cnt;
int n;
bool vis[12][12]={false};
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int c3[12];//c3[i]記錄 3^i
//估價函數為g(x)=c0(x)-c1(x);狀态x的情況下 0的個數-1的個數
struct Point{
    int x,y;
    int score;
    Point(){}
    Point(int a,int b,int c){x=a;y=b;score=c;}
}dp[60000];
bool cmp(struct Point Z,int i)
{
	int xx=empty[i]/n,yy=empty[i]%n;
	if(xx!=Z.x)return xx<Z.x;
	return yy<Z.y;
}
void init()
{
   cnt=0;
}
bool check(int x,int y){
    if(x<0||x>=n||y<0||y>=n)return 0;
    return 1;
}
int xx=0;
void dfs(int x,int y,int c)
{
    vis[x][y]=1;
    xx++;
    for(int i=0;i<4;i++){
        int x1=x+dx[i],y1=y+dy[i];
        if(check(x1,y1)&&!vis[x1][y1]&&map[x1][y1]==c+'0'){
            dfs(x1,y1,c);
        }
    }
}
int getsum()
{
    memset(vis,0,sizeof(vis));
    int c0=0,c1=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!vis[i][j]){
                xx=0;
                if(map[i][j]=='0')dfs(i,j,0),c0=MAX(c0,xx);
                else if(map[i][j]=='1') dfs(i,j,1),c1=MAX(c1,xx);
            }
        }
    }
    return c0-c1;//估價函數
}
struct Point MaxSearch(int state,int now,int pos);
struct Point MinSearch(int state,int now,int pos);
struct Point MaxSearch(int state,int now,int pos){//state為目前棋盤是否填充的二進制狀态。now為填充棋盤的三進制狀态
    struct Point Z,Y;
	if(state==0){
		Z.score=getsum();
		Z.x=empty[pos]%n;Z.y=empty[pos]/n;
		return Z;
	}
	if(dp[now].score!=-INF)return dp[now];
	int st=state;
	Z.score=-INF;//ans為本層最優值。
	while(st)
	{
		int k=st&(-st),cur;//k為最右邊的1，即從右往左依次選擇空棋盤位置。
		for(cur=0;cur<cnt;cur++){
			if((1<<cur)&k)break;
		}
		map[empty[cur]/n][empty[cur]%n]='0';
		Y=MinSearch(state^k,now+c3[cur],cur);
		map[empty[cur]/n][empty[cur]%n]='.';
		if(Z.score<Y.score||(Z.score==Y.score&&cmp(Z,cur)))Z.score=Y.score,Z.x=empty[cur]/n,Z.y=empty[cur]%n;
		st-=k;
	}
	return dp[now]=Z;
}
struct Point MinSearch(int state,int now,int pos)
{
	struct Point Z,Y;
	if(state==0){
		Z.score=getsum();
		Z.x=empty[pos]%n;Z.y=empty[pos]/n;
		return Z;
	}
	if(dp[now].score!=-INF)return dp[now];
	int st=state;
	Z.score=INF;//ans為本層最優值。
	while(st)
	{
		int k=st&(-st),cur;//k為最右邊的1，即從右往左依次選擇空棋盤位置。
		for(cur=0;cur<cnt;cur++){
			if((1<<cur)&k)break;//cur為從右數的空位标号。
		}
		map[empty[cur]/n][empty[cur]%n]='1';
		Y=MaxSearch(state-k,now+2*c3[cur],cur);
		map[empty[cur]/n][empty[cur]%n]='.';
		if(Z.score>Y.score||(Z.score==Y.score&&cmp(Z,cur)))Z.score=Y.score,Z.x=empty[cur]/n,Z.y=empty[cur]%n;
		st-=k;
	}
	return dp[now]=Z;
}
void input()
{
	int cnt0,cnt1;
	cnt0=cnt1=0;
    for(int i=0;i<n;i++){
        scanf("%s",map[i]);
        for(int j=0;j<n;j++)
        {
            if(map[i][j]=='1')cnt1++;
            if(map[i][j]=='0')cnt0++;
            if(map[i][j]=='.')empty[cnt++]=i*n+j;
        }
    }
	if(cnt0>cnt1){//都改成0為先手
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(map[i][j]=='0')map[i][j]='1';
				else if(map[i][j]=='1')map[i][j]='0';
			}
		}
	}
	for(int i=0;i<c3[cnt];i++)dp[i].score=-INF;
}
int main()
{
	c3[0]=1;
	for(int i=1;i<=10;i++)
		c3[i]=c3[i-1]*3;
    while(scanf("%d",&n)!=EOF&&n){
        init();
        input();
        Point ans=MaxSearch((1<<cnt)-1,0,0);
        printf("(%d,%d) %d\n",ans.x,ans.y,ans.score);
    }
    return 0;
}