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;
	}
};