POJ.3254 Corn Fields

1.Problem
http://poj.org/problem?id=3254

2.Idea
bit DP

3.Source

 int field[13] = { 0 };  
 int dp[13][4096];  
 int R, C, C2;  
 vector<int> seq;  
 void solve()  
 {  
      for (int i = 0; i < R; i++)  
           for (int j = 0; j < C; j++) {  
                int tmp;  
                cin >> tmp;  
                if (!tmp) field[i + 1] |= 1 << j;  
           }  
      for (int i = 0; i < C2; i++) {  
           if (!(i & (i << 1))) seq.push_back(i);  
      }  
      fill(dp[0], dp[0] + C2, 1);  
      for (int i = 1; i <= R; i++) {  
           fill(dp[i], dp[i] + C2, 0);  
           for (int j = 0; j < C2; j++) {  
                if (~j & field[i]) continue;  
                for (int k = 0; k < seq.size(); k++) {  
                     int u = seq[k];  
                     if (u & j) continue;  
                     dp[i][j] += dp[i - 1][u | field[i - 1]];  
                     dp[i][j] %= 100000000;  
                }  
           }  
      }  
      cout << dp[R][field[R]] << endl;  
 }  
 int main()  
 {  
      cin >> R >> C;  
      C2 = 1 << C;  
      solve();  
      return 0;  
 }