問題概要
迷路が与えられる。スタート地点からゴール地点へ移動する最小手数を求めよ。(問題文参照)
解法
問題文に記述されたアルゴリズム(幅優先探索)を用いることで解くことができます。
キューの使い方に関して詳しく述べておくと、新たに発見した地点をキューで管理することで、スタート地点から近い順に取り出すことができます。
コード
using VI = vector<int>; using VVI = vector<VI>; using VS = vector<string>; using PII = pair<int,int>; template < typename T = int > using LIM = numeric_limits<T>; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( e, c ) for ( auto &e : c ) #define MP( a, b ) make_pair( ( a ), ( b ) ) #define fst first #define snd second constexpr int dy[] = { 1, 0, -1, 0 }; constexpr int dx[] = { 0, 1, 0, -1 }; int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); int h, w, sy, sx, gy, gx; cin >> h >> w >> sy >> sx >> gy >> gx; VS board( h ); FOR( row, board ) { cin >> row; } queue<PII> que; que.push( MP( sy - 1, sx - 1 ) ); VVI distances( h, VI( w, LIM<>::max() ) ); distances[ sy - 1 ][ sx - 1 ] = 0; while ( !que.empty() ) { const PII cur = que.front(); que.pop(); REP( d, 0, 4 ) { const PII next( cur.fst + dy[d], cur.snd + dx[d] ); if ( board[ next.fst ][ next.snd ] == '.' && distances[ cur.fst ][ cur.snd ] + 1 < distances[ next.fst ][ next.snd ] ) { distances[ next.fst ][ next.snd ] = distances[ cur.fst ][ cur.snd ] + 1; que.push( next ); } } } cout << distances[ gy - 1 ][ gx - 1 ] << endl; return 0; }