AOJ 0223 Stray Twins
方針
ちゃんと問題文を読まなければいけない(反省).
というより,なんで座標(1, 1)から始まるんだ(憤怒).
幅優先探索です.
コード
const int dx[][4] = {{1, 0, -1, 0}, {-1, 0, 1, 0}}; const int dy[][4] = {{0, 1, 0, -1}, {0, -1, 0, 1}}; int X, Y; bool map[50][50]; bool passed[50][50][50][50]; struct P { int tx, ty; int kx, ky; int cost; P(int _tx, int _ty, int _kx, int _ky, int _cost) : tx(_tx), ty(_ty), kx(_kx), ky(_ky), cost(_cost) {}; }; bool check(int x, int y) { return x < 0 || x >= X || y < 0 || y >= Y || map[y][x]; } int main() { int tx, ty, kx, ky, ans; while(cin >> X >> Y, X|Y) { ans = -1; memset(passed, 0, sizeof passed); queue<P> que; cin >> tx >> ty >> kx >> ky; tx--, ty--, kx--, ky--; for(int i = 0; i < Y; i++) for(int j = 0; j < X; j++) cin >> map[i][j]; passed[tx][ty][kx][ky] = true; for(que.push(P(tx, ty, kx, ky, 0)); !que.empty(); que.pop()) { P p = que.front(); if(p.cost >= 100) break; if(p.tx == p.kx && p.ty == p.ky) { ans = p.cost; break; } for(int i = 0; i < 4; i++) { int mtx = p.tx + dx[0][i], mty = p.ty + dy[0][i]; int mkx = p.kx + dx[1][i], mky = p.ky + dy[1][i]; if(check(mtx, mty)) mtx = p.tx, mty = p.ty; if(check(mkx, mky)) mkx = p.kx, mky = p.ky; if(passed[mtx][mty][mkx][mky]) continue; passed[mtx][mty][mkx][mky] = true; que.push(P(mtx, mty, mkx, mky, p.cost + 1)); } } if(ans == -1) puts("NA"); else cout << ans << endl; } }