SRM504 Div1 Medium

500

入力の大きさを見てDPを捨てる。

H-1行目を埋める段階では、H-2行目が確定している。下から上へ見て行って良い気がする。
とりあえず逆から見ていったらサンプルが合う。通る。

class AlgridTwo {
public:
  int makeProgram(vector <string> t)
  {
    const lli mod = 1000000007;
    const int H = t.size();
    const int W = t[0].size();

    for (int i = H - 2; 0 <= i; --i) {
      for (int j = W - 2; 0 <= j; --j) {
        // cout << i << ' ' << j << endl;
        char& A = t[i][j];
        char& B = t[i][j + 1];
        char& C = t[i + 1][j];
        char& D = t[i + 1][j + 1];
        if (false) {
        } else if (A == 'W' && B == 'W') { // nothing
        } else if (A == 'B' && B == 'B') { // swap
          swap(C, D);
        } else if (A == 'B' && B == 'W') { // BB
          if (C == 'W' || D == 'W') return 0;
          C = D = '@';
        } else if (A == 'W' && B == 'B') { // WW
          if (C == 'B' || D == 'B') return 0;
          C = D = '@';
        } else ;
      }
    }

    int cnt = 0;
    for (int i = 0; i < t.size(); ++i) {
      cnt += count(t[i].begin(), t[i].end(), '@');
    }
    lli ret = 1;
    for (int i = 0; i < cnt; ++i) {
      ret = (ret * 2) % mod;
    }
    return ret;
  }
};