[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
#include <iostream> #include <queue> #include <map> #define INF (1<<21) using namespace std; typedef pair<int, int> Point; typedef pair<point, point> PSet; const int vx[4] = { 1, -1, 0, 0 }, vy[4] = { 0, 0, 1, -1 }; int X, Y; int maze[50][50]; Point T, K; bool isBlock( Point t ) { int x = t.first, y = t.second; if( x < 0 || X <= x || y < 0 || Y <= y ) return true; return maze[y][x]; } int bfs() { queue<pset> Q; map<pset, int> Time; map<pset, bool> M; PSet p, q; p.first = T; p.second = K; Q.push( p ); Time[p] = 0; M[p] = true; while( !Q.empty() ) { p = Q.front(); Q.pop(); int tx = p.first.first, ty = p.first.second, kx = p.second.first, ky = p.second.second; if( tx == kx && ty == ky ) return Time[p]; if( Time[p] >= 100 ) break; for( int i = 0; i < 4; i++ ) { q.first = Point( tx + vx[i], ty + vy[i] ); q.second = Point( kx - vx[i], ky - vy[i] ); if( isBlock( q.first ) ) q.first = Point( tx, ty ); if( isBlock( q.second ) ) q.second = Point( kx, ky ); if( !M[q] ) { Q.push( q ); M[q] = true; Time[q] = Time[p] + 1; } } } return INF; } main() { while( cin >> X >> Y && X && Y ) { int tx, ty, kx, ky; cin >> tx >> ty >> kx >> ky; T.first = tx - 1; T.second = ty - 1; K.first = kx - 1; K.second = ky - 1; for( int i = 0; i < Y; i++ ) for( int j = 0; j < X; j++ ) cin >> maze[i][j]; int time = bfs(); if( time != INF ) cout << time << endl; else cout << "NA" << endl; } }
COMMENT