SRM504 Div1 Medium

500

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

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

view plainprint?

1. class AlgridTwo {  
2. public:  
3.   int makeProgram(vector <string> t)  
4.   {  
5.     const lli mod = 1000000007;  
6.     const int H = t.size();  
7.     const int W = t[0].size();  
8.   
9.     for (int i = H - 2; 0 <= i; --i) {  
10.       for (int j = W - 2; 0 <= j; --j) {  
11.         // cout << i << ' ' << j << endl;  
12.         char& A = t[i][j];  
13.         char& B = t[i][j + 1];  
14.         char& C = t[i + 1][j];  
15.         char& D = t[i + 1][j + 1];  
16.         if (false) {  
17.         } else if (A == 'W' && B == 'W') { // nothing  
18.         } else if (A == 'B' && B == 'B') { // swap  
19.           swap(C, D);  
20.         } else if (A == 'B' && B == 'W') { // BB  
21.           if (C == 'W' || D == 'W') return 0;  
22.           C = D = '@';  
23.         } else if (A == 'W' && B == 'B') { // WW  
24.           if (C == 'B' || D == 'B') return 0;  
25.           C = D = '@';  
26.         } else ;  
27.       }  
28.     }  
29.   
30.     int cnt = 0;  
31.     for (int i = 0; i < t.size(); ++i) {  
32.       cnt += count(t[i].begin(), t[i].end(), '@');  
33.     }  
34.     lli ret = 1;  
35.     for (int i = 0; i < cnt; ++i) {  
36.       ret = (ret * 2) % mod;  
37.     }  
38.     return ret;  
39.   }  
40. };  

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