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; }