TopCoder SRM 423 Div1 Medium TheEasyChase

問題

nxnのチェス盤と二つの駒を使って二人が次のようなゲームをする。

• 最初先手の駒は(y1,x1)の位置に、後手の駒は(y2,x2)の位置におかれている。
• 二人は交互に、駒を上下左右の好きな方向へ、先手は1歩、後手は1歩または2歩動かす。
• 相手の駒を取ったプレイヤーの勝ち。
• お互いのプレイヤーは最善をつくす（勝てるなら最短手数で勝つことをめざし、負けるときはなるべく長い手数で負けることを目指す）

nおよびy1,x1,y2,x2が与えられるとき、
お互いが最善を尽くすとしてどちらが何手目で勝つかを求めよ。

制約条件

n≦20

方針

先手が一手で勝てる場合を除き必ず後手必勝になるクソゲーである。

ゲームの探索であるが、無限ループに入る可能性があることが普通と少し違う。

勝ち負けの確定した状態のノードはわかっているので、
そこからベルマンフォードっぽく勝ち負けを確定させていく。

遷移の仕方は普通のゲーム木の探索と同じで、先手負けに遷移できるならば先手の勝ち、
先手の勝ちにしか遷移できないなら先手の負け。
まだ不明な場合は不明にしておく。

ソースコード

const int dy[]={-1,0,1,0,-2,0,2,0},dx[]={0,-1,0,1,0,-2,0,2};
int dp[2][400][400];

class TheEasyChase {
	public:
	string winner(int n, int y1, int x1, int y2, int x2) 
	{
		rep(k,2)rep(i,400)rep(j,400)dp[k][i][j]=-inf;
		rep(k,2)rep(i,n)rep(j,n)dp[k][i*n+j][i*n+j]=0;
		for(;;){
			bool update=0;
			rep(p,2)rep(i,n)rep(j,n)rep(k,n)rep(l,n)
			if(dp[p][i*n+j][k*n+l]==-inf){
				bool unknown=0;
				int ans=inf;
				rep(d,(p?8:4)){
					int ny=i+dy[d], nx=j+dx[d], np=1-p;
					if(ny<0||nx<0||ny>=n||nx>=n)continue;
					int next=dp[np][k*n+l][ny*n+nx];
					if(next==-inf)unknown=1;
					else{
						if(ans==inf||ans<0&&next<=0)ans=-next;
						else if(ans>=0&&next<=0)ans=min(ans,-next);
						else if(ans<0)ans=min(ans,-next);
					}
				}
				if(ans!=inf&&ans>=0){
					dp[p][i*n+j][k*n+l]=ans+1;
					update=1;
				}
				else if(!unknown){
					dp[p][i*n+j][k*n+l]=ans-1;
					update=1;
				}
			}
			if(!update)break;
		}
		y1--; x1--; y2--; x2--;
		stringstream ss;
		ss<<(dp[0][y1*n+x1][y2*n+x2]>0?"WHITE":"BLACK")
			<<" "<<abs(dp[0][y1*n+x1][y2*n+x2]);
		return ss.str();
	}
};