SRM578 Div1 Easy

250

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

view plainprint?

1. class GooseInZooDivOne {  
2. public:  
3.   int count(vector <string> g, int dist)  
4.   {  
5.     const int H = g.size();  
6.     const int W = g[0].size();  
7.   
8.     vector< pair<int, int> > v;  
9.     for (int i = 0; i < H; ++i) {  
10.       for (int j = 0; j < W; ++j) {  
11.         if (g[i][j] == 'v') {  
12.           v.push_back(make_pair(i, j));  
13.         }  
14.       }  
15.     }  
16.     if (v.size() == 0) return 0;  
17.   
18.     const int N = v.size();  
19.     UnionFind uf(N);  
20.     for (int i = 0; i < N; ++i) {  
21.       uf.make(i);  
22.     }  
23.   
24.     for (int i = 0; i < N; ++i) {  
25.       for (int j = i + 1; j < N; ++j) {  
26.         int a = v[i].first - v[j].first;  
27.         int b = v[i].second - v[j].second;  
28.         if (abs(a) + abs(b) <= dist) {  
29.           uf.unite(i, j);  
30.         }  
31.       }  
32.     }  
33.   
34.     for (int i = 0; i < N; ++i) {  
35.       for (int j = 0; j < N; ++j) {  
36.         uf.isSameSet(i, j);  
37.         uf.find(i);  
38.       }  
39.     }  
40.     map<int, int> m;  
41.     for (int i = 0; i < N; ++i) {  
42.       ++m[uf.find(i, false)];  
43.     }  
44.     vector<int> u;  
45.     each (i, m) {  
46.       u.push_back(i->second);  
47.     }  
48.   
49.     lli dp[2][2];  
50.     dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = 0;  
51.     dp[0][0] = 1;  
52.   
53.     int curr = 0;  
54.     int next = 0;  
55.     for (int j = 0; j < u.size(); ++j) {  
56.       curr = j % 2;  
57.       next = (curr + 1) % 2;  
58.       dp[next][0] = dp[next][1] = 0;  
59.       for (int k = 0; k <= 1; ++k) {  
60.         dp[next][k] += dp[curr][k];  
61.         dp[next][k] %= mod;  
62.         dp[next][(k + u[j]) % 2] += dp[curr][k];  
63.         dp[next][k] %= mod;  
64.       }  
65.     }  
66.     return (dp[next][0] + mod - 1) % mod;  
67.   }  
68. }  

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