Problem 0223 : Stray Twins

問題概要

日本語なので本文参照（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0223&lang=jp）

w*h枚の正方形からなる長方形のグリッドであらわされるデパートに双子がいる。
デパートにはいくつかの障害物が存在する。
双子は上下左右に動けるが、一方は他方のちょうど逆の方向にしか動けない。
このとき、双子が同じマスに至るまでの最短の移動回数を求めよ。

解法

兄弟の位置をペアにしたノードについて幅優先探索をすればよい。
状態数は50*50*50*50で600万程度であるため十分間に合う。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int w,h,tx,ty,kx,ky;
int f[50][50];
bool v[50][50][50][50];

int main()
{
	while(scanf("%d%d",&w,&h),w)
	{
		scanf("%d%d%d%d",&tx,&ty,&kx,&ky);
		tx--; ty--; kx--; ky--;
		rep(i,h)rep(j,w)scanf("%d",f[i]+j);
		rep(i,h)rep(j,w)rep(k,h)rep(l,w)v[i][j][k][l]=0;
		
		v[tx][ty][kx][ky]=1;
		queue<pair<pair<pi,pi>,int> >Q;
		Q.push(mp(mp(mp(tx,ty),mp(kx,ky)),0));
		while(!Q.empty())
		{
			tx=Q.front().first.first.first; ty=Q.front().first.first.second;
			kx=Q.front().first.second.first; ky=Q.front().first.second.second;
			int cc=Q.front().second; Q.pop();
			
			rep(d,4)
			{
				int ntx=tx+dx[d],nty=ty+dy[d];
				int nkx=kx-dx[d],nky=ky-dy[d];
				
				if(ntx<0||ntx>=w||nty<0||nty>=h||f[nty][ntx])ntx=tx,nty=ty;
				if(nkx<0||nkx>=w||nky<0||nky>=h||f[nky][nkx])nkx=kx,nky=ky;
				if(v[ntx][nty][nkx][nky]||cc>=99)continue;
				if(ntx==nkx&&nty==nky)
				{
					printf("%d\n",cc+1); goto END;
				}
				Q.push(mp(mp(mp(ntx,nty),mp(nkx,nky)),cc+1));
				v[ntx][nty][nkx][nky]=1;
			}
		}
		puts("NA"); END:;
	}
	return 0;
}