TopCoder SRM 581 Div1 Hard YetAnotherBoardGame
問題
hxwのボードがあり、それぞれのマスは'W'または'B'
以下の操作を好きなだけ行うことができる。
- 種類1: マス(i, j)を選び、その隣接する4マスの色を全て反転させる。
- 種類2: マス(i, j)を選び、その隣接する4マスおよび(i, j)の色を全て反転させる。
色の反転とは、'W'だったマスは'B'に、'B'だったマスは'W'に変えることを言う。
隣接するマスが盤の外にはみ出る場合でも操作は有効で、はみ出たマスについてだけ無視される。
同じ行に、異なる二つの種類の操作を行うことはできない。
同じ列に、異なる二つの種類の操作を行うことはできない。
(したがって、一つのマスに二種類の操作を行うこともできない)
全てのマスを'B'にするために必要な操作の回数の最小値は何回か求めよ。
全てのマスを'B'にすることができないときは-1を返せ。
制約条件
W, H≦13
方針
ソースコード
const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1}; int h, w, b[13]; void flip(int c[13], int y, int x, int type){ rep(d, 4){ int ny = y + dy[d], nx = x + dx[d]; if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue; c[ny] ^= 1 << nx; } if(type == 2) c[y] ^= 1 << x; } int doit(int type1, int init){ int c[13] = {}; int res = 0; rep(i, h) c[i] = b[i]; rep(i, w) if(init >> i & 1){ flip(c, 0, i, type1 & init ? 1 : 2); res++; } for(int i = 1; i < h; i++){ bool used[3] = {}; rep(j, w) if(c[i - 1] >> j & 1){ flip(c, i, j, type1 & 1 << j ? 1 : 2); res++; used[type1 & 1 << j ? 1 : 2] = 1; } if(used[1] && used[2]) return inf; } rep(i, h) if(c[i]) return inf; return res; } class YetAnotherBoardGame { public: int minimumMoves(vector <string> board) { h = board.size(); w = board[0].size(); rep(i, h){ b[i] = 0; rep(j, w) b[i] |= (board[i][j] == 'W') << j; } int ans = inf; rep(type1, 1 << w){ for(int mask = type1; ; mask = type1 & (mask - 1)){ ans = min(ans, doit(type1, mask)); if(mask == 0) break; } int co = (1 << w) - 1 - type1; for(int mask = co; ; mask = co & (mask - 1)){ ans = min(ans, doit(type1, mask)); if(mask == 0) break; } } return ans == inf ? -1 : ans; } };