1178 Camelot

問題概要

チェスの盤にナイトがいくつかとキングが1つ置いてある。
これらを一つのマスへ集めるのにかかる手数の最小値を求めよ。

ただし、コマは以下のように動かせるものとする。

• ナイト、キングの動き方は通常のチェスと同じ
• 複数のコマが同時に同じマスに入ることができる
• 一つ以上のナイトとキングが同じマスにあるとき、(一つのナイトと)キングをナイトと一緒に動かすことができる（まとめて一手と数える）

解法

キングのマスへナイトが迎えに行って戻ることを考える。
ナイトは行って戻るのに2*k手が必要で、2*k手をかけるとキングは自分でそのマスへ向かうことができてしまう。

したがってキングの動きとして考える必要があるのは、直接目的地へ向かうか、ナイトが最短経路へ向かう途中で"ナイトに乗る"ような場合のみである。

後者は、ナイトの移動について、
(初期位置から途中のマスへの最短移動回数)+(途中のマスから目的地への最短移動回数)=(初期位置から目的地への最短移動回数)
の関係が成り立っていれば、最短経路の途中であると判定できる。

ナイトでの最短距離はあらかじめワーシャルフロイドなどで求めておく。

ソースコード

int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={-1,-2,-2,-1,1,2,2,1};
int n,X[64],Y[64],d[64][64];

int main()
{
	rep(i,64)rep(j,64)d[i][j]=i==j?0:inf;
	rep(i,8)rep(j,8)rep(k,8)
	{
		int y=i+dy[k],x=j+dx[k];
		if(y<0||y>=8||x<0||x>=8)continue;
		d[i*8+j][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]);
	
	char in[200]; scanf("%s",in);
	for(int i=0;in[i];i+=2,n++)
	{
		X[n]=in[i]-'A'; Y[n]=in[i+1]-'1';
	}
	
	int ans=inf;
	rep(y,8)rep(x,8)
	{
		int s=0,king=inf;
		for(int i=1;i<n;i++)
		{
			s+=d[y*8+x][Y[i]*8+X[i]];
			int mn=inf;
			rep(j,8)rep(k,8)if(d[y*8+x][Y[i]*8+X[i]]>=d[j*8+k][Y[i]*8+X[i]]+d[j*8+k][y*8+x])
			king=min(king,abs(Y[0]-j)+abs(X[0]-k));
		}
		ans=min(ans,s+king);
	}
	printf("%d\n",ans);
	return 0;
}