TopCoder SRM 594, Division 1, Level 2 : FoxAndGo3

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706

概要

'.', 'x', 'o' からなる盤面が与えられる。
盤面上のセル同士が辺を共有するとき、それらは隣接していると見做される。
与えられる状態で 'o' 同士は隣接していない。
'.' の場所に 'x' を置くことができて、'o' の近傍が全て 'x' になれば、その 'o' は取り除かれる。
最大でいくつの '.' を作ることができるか求めよ。

解法

元から 'x' のところはどうしようもないので除外して考えると、残りは '.' と 'o' になります。
以下、あるセルを最終的に '.' にすることを「得点する」と書きます。

'.' と 'o' の関係性に着目すると次のようになります。

• '.' で得点する場合、隣接する 'o' では得点できない
• 'o' で得点する場合、隣接する '.' では得点できない

問題は、この制約下で得点するセルを選ぶ問題と言い換えられます。
これは安定集合であるため、問題は最大安定集合に帰着されます。

ところで、辺は異なる種類同士を結ぶのでこれは二部グラフです。
二部グラフの場合、最大安定集合の大きさは　頂点数 - ｜最大マッチング｜　となります。
頂点数は 'x' でないセルの数です。

コード

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

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

// 二部グラフ最大マッチング O( |V||E| )
class BipartiteMatching;
// BipartiteMatching( |V| )
// connect( u, v )
// solve()

class FoxAndGo3
{
public:
	int maxEmptyCells( vector <string> board )
	{
		int H = board.size(), W = board[0].size();

		BipartiteMatching bm( H * W );

		int res = 0;
		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				res += board[i][j] != 'x';
				
				if ( board[i][j] == 'o' )
				{
					REP( d, 0, 4 )
					{
						const int y = i + dy[d];
						const int x = j + dx[d];

						if ( 0 <= y && y < H && 0 <= x && x < W && board[y][x] == '.' )
						{
							bm.connect( i * W + j, y * W + x );
						}
					}
				}
			}
		}
		
		return res - bm.solve();
	}
};