TopCoder SRM 266 Div1 Hard AntiChess

問題

以下のような自殺チェスを考える。

• 最初、白は盤上にn個のポーンをもち、それぞれの座標が与えられる
• 黒は1つのクイーンを持ち、その座標が与えられる
• 最初は白の手番
• プレイヤーは取れる駒があったら必ず駒を取らなければならない。複数の駒を取れるときはどれをとってもよい
• 黒が駒を取れなくなったり、合法手がなくなったり、駒がなくなったりしたら終了
• ポーンは前1マスに進める。ただし2列目にいるときは2マス進める
• ポーンが駒を取るときには、斜め前に1マス進む

黒は取られるポーンの数が最大になるように、
白は取るポーンの数が最小になるように手を選ぶものとするとき、
いくつのポーンが取られるか、求めよ。

制約条件

ポーンの数≦8

方針

メモ化して通常のゲーム木探索をすればよい。

ソースコード

const int dy[]={-1,0,1,0,1,1,-1,-1},dx[]={0,-1,0,1,1,-1,1,-1};
map<pi,int> dp;
int rec(ll board,int qq,int turn){
	int q=qq*2+turn;
	if(dp.count(mp(board,q)))return dp[mp(board,q)];
	if(!turn){
		rep(i,8)rep(j,7)if(board&1ll<<i*8+j)
		if(i+1==qq/8&&j+1==qq%8||i-1==qq/8&&j+1==qq%8)return dp[mp(board,q)]=0;
		int res=0;
		rep(i,8)rep(j,7)if((board&1ll<<i*8+j)&&!(board&1ll<<i*8+j+1)&&!(i*8+j+1==qq)){
			ll next=board^(1ll<<i*8+j)|(1ll<<i*8+j+1);
			res=max(res,rec(next,qq,1-turn));
			
			if(j==1&&!(board&1ll<<i*8+j+2)&&!(i*8+j+2==qq)){
				ll next=board^(1ll<<i*8+j)|(1ll<<i*8+j+2);
				res=max(res,rec(next,qq,1-turn));
			}
		}
		return dp[mp(board,q)]=res;
	}
	int x=qq/8, y=qq%8, res=inf;
	rep(d,8){
		int ny=y, nx=x;
		for(;;){
			ny+=dy[d]; nx+=dx[d];
			if(ny<0||nx<0||ny>=8||nx>=8)break;
			if(board&1ll<<nx*8+ny){
				ll next=board^1ll<<nx*8+ny;
				res=min(res,1+rec(next,nx*8+ny,1-turn));
				break;
			}
		}
	}
	if(res==inf)res=0;
	return dp[mp(board,q)]=res;
}
class AntiChess {
	public:
	int sacrifice(vector <string> white, string black) 
	{
		ll board=0;
		rep(i,white.size()){
			int a=white[i][0]-'a', b=white[i][1]-'1';
			board|=1ll<<a*8+b;
		}
		dp.clear();
		return rec(board,(black[0]-'a')*8+black[1]-'1',0);
	}
};