AtCoder Beginner Contest 176, D : Wizard in Maze

問題文

　https://atcoder.jp/contests/abc176/tasks/abc176_d

問題概要

　$H \times W$ のグリッド状の迷路がある．迷路の各セルは，通路または障害物で，立ち入ることができるのは盤内の通路セルのみである．
　ここで，以下の 2 種類の移動をすることができる．

• 上下左右に隣接するセルへ，コスト $0$ で移動する
• 現在位置を中心とする $5 \times 5$ の範囲内のセルへ，コスト $1$ で移動する

　指定されたスタート位置から指定されたゴール位置へ移動するときの最小コストはいくらか？

制約

• $1 \leq H, W \leq 10^3$

解法

　この問題は，コストが $0$ または $1$ の最短経路問題として捉えることができます．これは，（俗に？）01-BFS と呼ばれる手法で解くことができ，今回の場合は $O( HW )$ 時間となります．

コード

constexpr auto INF = LIM<>::max() / 2;

constexpr int dy[] = { 0, 1, 0, -1 };
constexpr int dx[] = { 1, 0, -1, 0 };

int main()
{
	IN( int, H, W );
	IN( int, sy, sx, ty, tx );
	--sy, --sx, --ty, --tx;

	VS board( H );
	cin >> board;

	const auto inside = [&]( const int y, const int x )
	{
		return 0 <= y && y < H && 0 <= x && x < W;
	};

	const auto road = [&]( const int y, const int x )
	{
		return inside( y, x ) && board[y][x] == '.';
	};

	deque< PII > que;
	que.EB( sy, sx );

	VVI distances( H, VI( W, INF ) );
	distances[ sy ][ sx ] = 0;

	while ( !que.empty() )
	{
		const int y = que.front().fst;
		const int x = que.front().snd;
		que.pop_front();

		REP( d, 4 )
		{
			const int ny = y + dy[d];
			const int nx = x + dx[d];
			if ( road( ny, nx ) && chmin( distances[ ny ][ nx ], distances[y][x] ) )
			{
				que.emplace_front( ny, nx );
			}
		}
		REP( i, -2, 3 )
		{
			REP( j, -2, 3 )
			{
				const int ny = y + i;
				const int nx = x + j;		
				if ( road( ny, nx ) && chmin( distances[ ny ][ nx ], distances[y][x] + 1 ) )
				{
					que.EB( ny, nx );
				}
			}
		}
	}

	const int res = distances[ ty ][ tx ];
	cout << ( res == INF ? -1 : res ) << endl;

	return 0;
}