SRM 578 Div1 Easy GooseInZooDivOne

問題

2次元グリッドが与えられる。'v'で与えられるセルにはガチョウかアヒルがいる。これらの鳥の配置には以下のようなルールがある。

1. 少なくとも1羽は必ずガチョウであり、必ず偶数羽いる
2. 互いにマンハッタン距離でdist以内にいる鳥はガチョウである

ガチョウの配置のパターン数を求めよ。

やりかた

まず幅優先探索か深さ優先探索で鳥群をリストアップする。鳥群は偶数羽の場合と奇数羽の場合がある。偶数羽の鳥群がA個、奇数羽の鳥群がB個できたときに、偶数羽の鳥群は（ガチョウは偶数羽いるという制約から）どれがガチョウであっても問題ない。そのため2^A個のパターンがある。奇数羽の鳥群は群のうち偶数個がガチョウ群でなければならない。そのためBC0 + BC2 + BC4 + BC6 + ...が配置のパターン数であるが、これはB-1個を任意に選ぶと残りの一つについてはB-1個の偶奇を調整するため自由度がないため2^(B-1)個になる。よってこの2つをかけあわせて、まったくガチョウがいないという1ケースをのぞいたが答えとなる。

以下ソース

class GooseInZooDivOne {
public:
  int count(vector <string> field, int dist) {
    int N = field.size(), M = field[0].length();
    vector<vector<int> > la(N, vector<int>(M, -1));

    int cnt = 0;
    for(int i = 0; i < N; i++){
      for(int j = 0; j < M; j++){
	if(la[i][j] != -1 || field[i][j] == '.') continue;
	queue<pair<int, int> > Q;
	Q.push(make_pair(i, j));
	la[i][j] = cnt;
	while(!Q.empty()){
	  int y = Q.front().first;
	  int x = Q.front().second;
	  Q.pop();
	  for(int dy = -dist; dy <= dist; dy++){
	    for(int dx = -dist; dx <= dist; dx++){
	      if(!(0 <= dy + y && dy + y < N && 0 <= dx + x && dx + x < M)) continue;
	      if(abs(dy) + abs(dx) <= dist && la[dy + y][dx + x] == -1 && field[dy + y][dx + x] == 'v'){
		Q.push(make_pair(dy + y, dx + x));
		la[dy + y][dx + x] = cnt;
	      }
	    }
	  }
	}
	cnt++;
      }
    }
    vector<int> mag(10000, 0);
    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++)
	if(la[i][j] >= 0) mag[la[i][j]]++;

    int odd = 0, even = 0;
    for(int i = 0; i < cnt; i++)
      if(mag[i] % 2 == 0) even++; 
      else odd++;

    ll e = 1; for(int i = 0; i < even; i++) e = (e * 2) % MOD;
    ll o = 1; for(int i = 0; i < odd - 1; i++) o = (o * 2) % MOD;
    return (e * o - 1) % MOD;
  }
};