poj3254 Corn Fields

思路：
状态压缩dp。
实现：
 1 #include <iostream>
 2 using namespace std;
 3 const int MOD = 100000000;
 4 int m, n, a[13][13], dp[13][13][1 << 13];
 5 int main()
 6 {
 7     cin >> m >> n;
 8     for (int i = 0; i < m; i++)
 9     {
10         for (int j = 0; j < n; j++)
11         {
12             cin >> a[i][j];
13         }
14     }
15     for (int i = 0; i < 1 << n; i++)
16     {
17         bool flg = true;
18         for (int j = 0; j < n; j++)
19         {
20             if (a[m - 1][j] == 0 && i >> j & 1) 
21             {
22                 flg = false;
23                 break;
24             }
25         }
26         dp[m][0][i] = flg;
27     }
28     for (int i = m - 1; i >= 0; i--)
29     {
30         for (int j = n - 1; j >= 0; j--)
31         {
32             for (int k = 0; k < 1 << n; k++)
33             {
34                 int ni = i, nj = j + 1;
35                 if (j == n - 1) { ni = i + 1; nj = 0; }
36                 dp[i][j][k] += dp[ni][nj][k & ~(1 << j)];
37                 dp[i][j][k] %= MOD;
38                 bool ok = true;
39                 if (a[i][j] == 0) ok = false;
40                 if (j && k >> (j - 1) & 1) ok = false;
41                 if (k >> j & 1) ok = false;
42                 if (ok) 
43                 {
44                     dp[i][j][k] += dp[ni][nj][k | 1 << j];
45                     dp[i][j][k] %= MOD;
46                 }
47             }
48         }
49     }
50     cout << dp[0][0][0] << endl;
51     return 0;
52 }