TopCoder SRM 488 Div 2 Hard SolitaireChess

TopCoder 動的計画法

問題概要

8x8のチェス盤にポーンまたはナイトが合計20個まで置かれた局面が2つある。
最初の局面から駒を動きに従って動かし、2番目の局面を作りたい。ただし、

  • 途中では駒と駒は何枚でも同じマスに重なることができる
  • ポーンは1列目まで動くとプロモーションしてナイトになる

ものとする。
このとき、2番目の局面を作るのに必要な最小手数を求めよ。
不可能な場合は-1と答えよ。

解法

ポーンの置き方はGreedyでよい。（下の列にあるものをなるべく下のポーンにうつす）
余ったポーンは1列目まで進めてプロモーションさせる。


するとナイトの対応のみを考えればよくなる。
駒は途中重なってもよいので、ナイトの到着点n個およびナイトの出発点n個を頂点とする二部グラフの重みマッチングに還元される。


n≦20と小さいので、これはO(n*2^n)のビットDPで解けばよい。

ソースコード

int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={-1,-2,-2,-1,1,2,2,1};
int d[64][64];
int n,e[20][20],dp[2][1<<20];

int solve()
{
	rep(j,1<<n)dp[0][j]=inf;
	dp[0][0]=0;
	
	int cur=0,next=1;
	
	rep(i,n)
	{
		rep(j,1<<n)dp[next][j]=inf;
		rep(j,1<<n)
		{
			if(dp[cur][j]!=inf)rep(k,n)if(!(j&1<<k)&&e[i][k]!=inf)
			dp[next][j|1<<k]=min(dp[next][j|1<<k],dp[cur][j]+e[i][k]);
		}
		swap(cur,next);
	}
	return dp[cur][(1<<n)-1];
}
class SolitaireChess {
	public:
	int transform(vector <string> board1, vector <string> board2) 
	{
		//ナイトの2マス間の必要移動回数はワーシャルフロイドなどであらかじめ求めておく。
		rep(i,64)rep(j,64)d[i][j]=i==j?0:inf;
		rep(i,64)rep(j,8)
		{
			int y=i/8+dy[j],x=i%8+dx[j];
			if(0<=y&&y<8&&0<=x&&x<8)d[i][y*8+x]=1;
		}
		rep(k,64)rep(i,64)rep(j,64)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		
		vi sy,sx,gy,gx; //出発点と到着点の座標のリスト
		rep(i,8)rep(j,8)
		{
			if(board1[i][j]=='N')sy.pb(i),sx.pb(j);
			if(board2[i][j]=='N')gy.pb(i),gx.pb(j);
		}
		
		int ans=0;
		rep(j,8)for(int i=7;i>=0;i--)if(board1[i][j]=='P')
		{
			for(int k=i+1;k<8;k++)if(board2[k][j]=='P')return -1;
			for(int k=i;k>=0;k--)if(board2[k][j]=='P')
			{
				board2[k][j]='.'; ans+=i-k;
				goto NEXT;
			}
			ans+=i;
			sy.pb(0); sx.pb(j); //余ったポーンはプロモーション
			NEXT:;
		}
		
		n=sy.size();
		if(n!=gy.size())return -1;
		
		rep(i,n)rep(j,n)e[i][j]=d[sy[i]*8+sx[i]][gy[j]*8+gx[j]];
		ans+=solve();
		
		return ans<inf?ans:-1;
	}