1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64#include <bits/stdc++.h>
using namespace std;

const int MOD = 100000000;

int n, m;
int a[15][15];
int used[15][15];
int ans;

bool ok_place(int x, int y) {
    if (a[x][y] == 0) {
        return false;
    }
    if (y > 1 && used[x][y - 1]) {
        return false;
    }
    if (x > 1 && used[x - 1][y]) {
        return false;
    }
    return true;
}

void dfs_cell(int pos) {
    if (pos == n * m) {
        ans++;
        if (ans >= MOD) {
            ans -= MOD;
        }
        return;
    }

    int x = pos / m + 1;
    int y = pos % m + 1;

    // 不在这个格子种草。
    dfs_cell(pos + 1);

    // 在这个格子种草。
    if (ok_place(x, y)) {
        used[x][y] = 1;
        dfs_cell(pos + 1);
        used[x][y] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：逐格枚举种或不种，用来帮助理解题意和辅助对拍。
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    memset(used, 0, sizeof(used));
    ans = 0;
    dfs_cell(0);
    cout << ans << '\n';
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82#include <bits/stdc++.h>
using namespace std;

const int MOD = 100000000;
const int MAXN = 15;
const int MAXS = 1 << 12;

int n, m;
int allow_mask[MAXN];        // allow_mask[i] 的 1 表示这一格可以种草
int states[MAXS], state_cnt; // 所有单行内部合法状态
int dp[2][MAXS];

bool ok_self(int s) {
    // 同一行里不能出现相邻的两块草地。
    return (s & (s << 1)) == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int mask = 0;
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            if (x == 1) {
                mask |= 1 << j;
            }
        }
        allow_mask[i] = mask;
    }

    int full = 1 << m;
    for (int s = 0; s < full; s++) {
        if (ok_self(s)) {
            states[state_cnt++] = s;
        }
    }

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int row = 1; row <= n; row++) {
        int now = row & 1;
        int pre = now ^ 1;
        memset(dp[now], 0, sizeof(dp[now]));

        for (int i = 0; i < state_cnt; i++) {
            int cur = states[i];
            // 当前行选的位置必须全部是可种草的土地。
            if ((cur & allow_mask[row]) != cur) {
                continue;
            }

            for (int j = 0; j < state_cnt; j++) {
                int last = states[j];
                // 上下两行不能在同一列都种草。
                if (cur & last) {
                    continue;
                }
                dp[now][cur] += dp[pre][last];
                if (dp[now][cur] >= MOD) {
                    dp[now][cur] -= MOD;
                }
            }
        }
    }

    int last = n & 1;
    int ans = 0;
    for (int i = 0; i < state_cnt; i++) {
        ans += dp[last][states[i]];
        if (ans >= MOD) {
            ans -= MOD;
        }
    }

    cout << ans << '\n';
    return 0;
}