概要
'.', '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(); } };