AOJ 0223 Stray Twins

明日、PCK本選です。
がんばります!

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0223

解法
地道に幅優先探索する。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int,int> P;
typedef pair<int , pair<P, P> > T;

const int INF = 1 << 29;
const int MAX_XY = 50;
char a[MAX_XY + 2][MAX_XY + 2];
bool ved[MAX_XY + 2][MAX_XY + 2][MAX_XY + 2][MAX_XY + 2];
int X, Y;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int solve(int tx, int ty, int kx, int ky){
	queue<T> Q;
	int ans = INF;
	Q.push(T(0, pair<P,P>(P(tx, ty), P(kx, ky))));
	ved[tx][ty][kx][ky] = true;
	while(!Q.empty()){
		T t = Q.front(); Q.pop();
		int d = t.first;
		P ta = t.second.first;
		P ka = t.second.second;
		//printf("d=%d (%d %d) (%d %d)\n", d, ta.first, ta.second, ka.first, ka.second);
		if(d + 1 >= 100) break;
		for(int i = 0; i < 4; i++){
			int ntx = ta.first + dx[i];
			int nty = ta.second + dy[i];
			int nkx = ka.first - dx[i];
			int nky = ka.second - dy[i];
			if(a[ntx][nty] == 1){
				ntx -= dx[i];
				nty -= dy[i];
			}
			if(a[nkx][nky] == 1){
				nkx += dx[i];
				nky += dy[i];
			}
			if(!ved[ntx][nty][nkx][nky] && a[ntx][nty] + a[nkx][nky] == 0){
				if(ntx == nkx && nky == nty)
					return d + 1;
				ved[ntx][nty][nkx][nky] = true;
				Q.push(T(d + 1, pair<P, P>(P(ntx,nty),P(nkx,nky))));
			}
		}
	}
	return -1;
}

int main(){
	while(scanf("%d %d", &X, &Y) && X != 0 ){
		int tx, ty, kx, ky;
		scanf("%d %d %d %d", &tx, &ty, &kx, &ky);
		for(int i =  0; i < X + 2; i++)
			for(int j =  0; j < Y + 2; j++)
				for(int k =  0; k < X + 2; k++)
					for(int l =  0; l < Y + 2; l++)
						ved[i][j][k][l] = false;
		for(int i = 0; i < Y + 2; i++){
			a[0][i] = 1;
			a[X + 1][i] = 1;
		}
		for(int j = 0; j < X + 2; j++){
			a[j][0] = 1;
			a[j][Y + 1] = 1;
		}
		for(int i = 0; i < Y; i++){
			for(int j = 0; j < X; j++){
				int t;
				scanf("%d", &t);
				a[j+1][i+1] = (char)t;
			}
		}
		int t = solve(tx,ty,kx,ky);
		if(t == -1)
			puts("NA");
		else
			printf("%d\n", t);
		
	}
	return 0;
}