TopCoder SRM 590, Division 2, Level 2 : FoxAndGo

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12743&rd=15702

概要

'.', 'x', 'o' からなるグリッド状の盤面が与えられる。
'o' の component を次のように定義する。

• 二つの 'o' が辺を共有して接しているとき、この二つは同じ component に属する
• 三つの 'o' A, B, C について A と B が同じ component に属し、B と C が同じ component に属するならば、 A と C は同じ component に属する

'.' を一つ 'x' に変える操作ができ、'.' に接さない component に属する 'o' の数が得点となる。
得られる得点の最大値を求めよ。

解法

盤面が狭いので、'x' を置く場所を全て試すことができます。
ある component に属する 'o' の数と、その component に接するセルの種類は一回の BFS / DFS で適当に数えられます。

コード

typedef vector<string> VS;
typedef pair<int,int> PII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

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

class FoxAndGo
{
public:
	int H, W;

	int maxKill( vector <string> board )
	{
		H = board.size(), W = board[0].size();

		int res = 0;
		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( board[i][j] != '.' )
				{
					continue;
				}
				VS tmp = board;
				tmp[i][j] = 'x';
				res = max( res, solve( tmp ) );
			}
		}

		return res;		
	}

	int solve( VS board )
	{
		int res = 0;

		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( board[i][j] != 'o' )
				{
					continue;
				}
				res += closed( board, i, j );
			}
		}

		return res;
	}		

	int closed( VS &board, int sy, int sx )
	{
		queue<PII> que;
		que.push( MP( sy, sx ) );

		set<PII> visited;
		visited.insert( MP( sy, sx ) );

		set<char> surround;

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

			if ( board[ cur.fst ][ cur.snd ] != 'o' )
			{
				surround.insert( board[ cur.fst ][ cur.snd ] );
			}
			else
			{
				res ++;
				board[ cur.fst ][ cur.snd ] = 'x';

				REP( d, 0, 4 )
				{
					PII next = cur;
					next.fst += dy[d];
					next.snd += dx[d];

					if ( inside( next.fst, next.snd ) && !EXIST( visited, next ) )
					{
						que.push( next );
						visited.insert( next );
					}
				}
			}
		}

		return surround.size() == 1 && *( surround.begin() ) == 'x' ? res : 0;
	};

	bool inside ( int y, int x )
	{
		return 0 <= y && y < H && 0 <= x && x < W;
	}
}