SRM578 Div1 Easy

250

マンハッタン距離が dist 以下の点同士をまとめておく。
"選ぶ" or "選ばない"の2択で偶数になる場合を数え上げる。
DP[どこまで見た][総和の遇奇]=パターン

class GooseInZooDivOne {
public:
  int count(vector <string> g, int dist)
  {
    const int H = g.size();
    const int W = g[0].size();

    vector< pair<int, int> > v;
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (g[i][j] == 'v') {
          v.push_back(make_pair(i, j));
        }
      }
    }
    if (v.size() == 0) return 0;

    const int N = v.size();
    UnionFind uf(N);
    for (int i = 0; i < N; ++i) {
      uf.make(i);
    }

    for (int i = 0; i < N; ++i) {
      for (int j = i + 1; j < N; ++j) {
        int a = v[i].first - v[j].first;
        int b = v[i].second - v[j].second;
        if (abs(a) + abs(b) <= dist) {
          uf.unite(i, j);
        }
      }
    }

    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        uf.isSameSet(i, j);
        uf.find(i);
      }
    }
    map<int, int> m;
    for (int i = 0; i < N; ++i) {
      ++m[uf.find(i, false)];
    }
    vector<int> u;
    each (i, m) {
      u.push_back(i->second);
    }

    lli dp[2][2];
    dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;
    dp[0][0] = 1;

    int curr = 0;
    int next = 0;
    for (int j = 0; j < u.size(); ++j) {
      curr = j % 2;
      next = (curr + 1) % 2;
      dp[next][0] = dp[next][1] = 0;
      for (int k = 0; k <= 1; ++k) {
        dp[next][k] += dp[curr][k];
        dp[next][k] %= mod;
        dp[next][(k + u[j]) % 2] += dp[curr][k];
        dp[next][k] %= mod;
      }
    }
    return (dp[next][0] + mod - 1) % mod;
  }
}