AtCoder Beginner Contest 184, E : Third Avenue

問題文

　https://atcoder.jp/contests/abc184/tasks/abc184_e

問題概要

　$H \times W$ のグリッド状の迷路がある．空きマスは，単なる空きマスと，英小文字が書き込まれたものがある．
　移動は

• 上下左右の隣接するマスへ移動する
• 現在地に書かれている文字と同じ文字が書かれた任意のマスへ移動する

　指定されたスタート地点からゴール地点へ到達するための移動回数の最小値はいくらか？

制約

• $1 \leq H, W \leq 2000$

解法

　2 種目の移動（以降ワープと呼ぶ）が無ければ，BFS の練習問題です．ワープがある場合も，（ワープのコストが $1$ なので）同様に BFS で解くことができます．ただし，盤面が ’a' で埋まっている場合などを想像すると分かるように，ワープの種類毎の位置のリストを何度も走査すると TLE してしまいます．しかしよく考えると，ワープは（同種のワープ地点の任意の位置に移動できるので）使うとすれば種類毎に高々 $1$ 回使えば十分です．よって，各ワープを使ったかどうかも同時に管理し，同じものを複数回使わないようにすることで，TLE を回避できます．計算量としては $O( HW )$ 時間になります．

コード

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

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

int main()
{
	cin.tie( nullptr );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	IN( int, H, W );
	VS board( H );
	cin >> board;

	const auto enterable = [&]( const int y, const int x )
	{
		return 0 <= y && y < H && 0 <= x && x < W && board[y][x] != '#';
	};

	map< char, VPII > chars;
	REP( i, H )
	{
		REP( j, W )
		{
			const char c = board[i][j];
			if ( isalpha( c ) )
			{
				chars[c].EB( i, j );
			}
		}
	}

	const int sy = begin( chars['S'] )->fst;
	const int sx = begin( chars['S'] )->snd;
	const int gy = begin( chars['G'] )->fst;
	const int gx = begin( chars['G'] )->snd;

	queue< PII > que;
	que.EM( sy, sx );
	VVI distances( H, VI( W, INF ) );
	distances[ sy ][ sx ] = 0;

	VI used( 256 );

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

		REP( d, 4 )
		{
			const int ny = y + dy[d];
			const int nx = x + dx[d];
			if ( enterable( ny, nx ) && chmin( distances[ ny ][ nx ], distances[y][x] + 1 ) )
			{
				que.EM( ny, nx );
			}
		}

		const char c = board[y][x];
		if ( !islower( c ) || used[c] )
		{
			continue;
		}
		used[c] = true;
		FOR( p, chars[c] )
		{
			const int ny = p.fst;
			const int nx = p.snd;
			if ( chmin( distances[ ny ][ nx ], distances[y][x] + 1 ) )
			{
				que.EM( ny, nx );
			}
		}
	}

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

	return 0;
}