TopCoder, SRM 637, Division 2, Level 2 : PathGameDiv2

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13506&rd=16080

問題概要

　グリッド状の盤面を使ったゲームをする。盤面の高さは 2 で固定であり、横の長さは正整数で表される。また、盤面上の各セルは黒または白に塗られている。初期状態でのカラーリングの状態は、文字列配列 によって耐えられる。
　盤面上のパスとは、セルの列（ sequence ）であって、

• 白いセルのみからなる
• 先頭が一番左の列（ column ）にある
• 末尾は一番右の列にある
• 隣接するセル同士は辺を共有している

もののことを言う。初期状態で、少なくとも 1 つのパスが存在する。
　ゲームの目的は、1 つ以上のパスが存在する状態を維持したまま、できるだけ多くの白いセルを黒に塗り替えることである。塗ることのできるセルの数の最大数を求めよ。

解法

　※ちょっと冗長な解き方です

　まず、2 つ以上のパスが存在するとき、パスのいずれかを消すような塗り替えにより、より多くのセルを塗ることができるので、最大の塗り替え数を達成したときの、盤面上に存在するパスの数は丁度 1 になっているはずです。従って、最後に残すパスが決まったとき、塗ることのできるセルは、そのパスに関係の無い全ての白いセルであると決まります。
　また、塗るという選択が可能なのは白いセルのみなので、できるだけ少ない数の白いセルを使って（最後に残す）パスを構成した方が、塗り替えられるセルの数が多くなります。このパスは、経路に含まれる白いセルの数を経路長とする最短経路問題を解くことで求めることができます。部分経路に新たに 1 つのセルを追加するときの経路長の増加が常に等しいので、BFS で求めることができます。

解法

using VI = vector<int>; using VVI = vector<VI>;
using PII = pair<int,int>; using VPII = vector< 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 ALL( c ) (c).begin(), (c).end()

#define EM emplace

#define fst first
#define snd second

const int INF = LIM<>::max() / 2;

class PathGameDiv2
{
public:
	int calc( vector <string> board )
	{
		const int H = 2, W = board[0].size();

		VVI dist( H, VI( W, INF ) );
		queue< PII > que;
		REP( i, 0, 2 )
		{
			if ( board[i][0] == '.' )
			{
				dist[i][0] = 1;
				que.EM( i, 0 );
			}
		}

		while ( !que.empty() )
		{
			const PII cur = que.front();
			que.pop();

			if ( cur.snd + 1 < W && board[ cur.fst ][ cur.snd + 1 ] == '.' && dist[ cur.fst ][ cur.snd ] + 1 < dist[ cur.fst ][ cur.snd + 1 ] )
			{
				dist[ cur.fst ][ cur.snd + 1 ] = dist[ cur.fst ][ cur.snd ] + 1;
				que.EM( cur.fst, cur.snd + 1 );
			}
			if ( board[ 1 - cur.fst ][ cur.snd ] == '.' && dist[ cur.fst ][ cur.snd ] + 1 < dist[ 1 - cur.fst ][ cur.snd ]  )
			{
				dist[ 1 - cur.fst ][ cur.snd ] = dist[ cur.fst ][ cur.snd ] + 1;
				que.EM( 1 - cur.fst, cur.snd );
			}
		}

		const int minimal = min( dist[0][ W - 1 ], dist[1][ W - 1 ] );
		return count( ALL( board[0] ), '.' ) + count( ALL( board[1] ), '.' ) - minimal;
	}
};