AtCoder Beginner Contest 339, D : Synchronized Players

問題文

　https://atcoder.jp/contests/abc339/tasks/abc339_d

問題概要

　$n \times n$ のグリッド状の盤面があり，各セルは空きマスまたは障害物である．また，2 つの駒が盤面の（相異なる）セルに置かれている．
　駒たちに対し，以下の操作を適用することができる：

1. 上下左右の方向をひとつ選ぶ．
2. 2 つの駒をその方向に 1 マス移動させる．
   • ただし，盤外に出たり障害物にめり込むような移動を試みた場合は，その場に留まる．

　2 つの駒が同じセルに存在するような状態にするために必要な操作回数の最小値はいくらか？

制約

• $2 \leq n \leq 60$

解法

　重み無しグラフの最短経路（とその距離）を求めるアルゴリズムとして「幅優先探索」(Breadth-First Search) というものが知られています．本問題は一見するとグラフの最短路には見えませんが，2 つの駒の位置をそれぞれ $( y_1, x_1 ), ( y_2, x_2 )$ だとして*1タプル $( y_1, x_1, y_2, x_2 )$ を頂点とするグラフを考える*2ことで，グラフの最短路と同様の解き方ができます．ここで，グラフの辺は問題文で言われている操作を一回適用した先の状態への有向辺となります．
　あとは，（ちょっと面倒ですが）BFS を書いてあげれば解を求めることができます．計算量については，駒の位置の組合せが $O( n^4 )$ 通りあり，各状態からの遷移は定数個なので $O( n^4 )$ 時間……ではなく，以下の例では距離の管理に std::map を使っているので $O( n^4 \log n )$ 時間となっていたのですが，配列というデータ構造があって，それを使うと O( n^4 ) 時間になります．

コード

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

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

int main()
{
	IN( int, N );
	VS board( N );
	cin >> board;

	VI players;
	REP( i, N )
	{
		REP( j, N )
		{
			if ( board[i][j] == 'P' )
			{
				players.PB( i );
				players.PB( j );
			}
		}
	}

	using State = tuple< int, int, int, int >;
	queue< State > que;
	que.EM( State( players[0], players[1], players[2], players[3] ) );

	static int distances[ 64 ][ 64 ][ 64 ][ 64 ];
	fill( AALL( distances ), INF );
	distances[ players[0] ][ players[1] ][ players[2] ][ players[3] ] = 0;

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

	while ( !que.empty() )
	{
		const int y1 = get< 0 >( que.front() );
		const int x1 = get< 1 >( que.front() );
		const int y2 = get< 2 >( que.front() );
		const int x2 = get< 3 >( que.front() );
		const int dist = distances[ y1 ][ x1 ][ y2 ][ x2 ];
		que.pop();

		if ( y1 == y2 && x1 == x2 )
		{
			cout << dist << endl;
			return 0;
		}

		REP( d, 4 )
		{
			int ny1 = y1 + dy[d], nx1 = x1 + dx[d],
				ny2 = y2 + dy[d], nx2 = x2 + dx[d];
			if ( !inside( ny1, nx1 ) || board[ ny1 ][ nx1 ] == '#' )
			{
				tie( ny1, nx1 ) = tie( y1, x1 );
			}
			if ( !inside( ny2, nx2 ) || board[ ny2 ][ nx2 ] == '#' )
			{
				tie( ny2, nx2 ) = tie( y2, x2 );
			}

			State next( ny1, nx1, ny2, nx2 );
			if ( chmin( distances[ ny1 ][ nx1 ][ ny2 ][ nx2 ], dist + 1 ) )
			{
				que.push( next );
			}
		}
	}

	cout << -1 << endl;

	return 0;
}

*1:プログラミングに寄せて $y$ を第一要素に置いています．

*2:別に順序対の順序対とかでもよいです．