摆摊地图，二维矩阵，每个格子0或1,，1可摆摊，0不可摆摊，相邻格子不可同时摆摊，问有多少种摆摊方案C++代码

好的，以下是 C++ 代码实现：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MOD = 987654321;
const int MAXN = 12;
const int MAXM = 1 << MAXN;

int n, m;
int dp[MAXN][MAXM][MAXM];

bool check(int p, int j, int k) {
    for (int i = 0; i < n; i++) {
        if ((p >> i) & 1) {
            if ((j >> i) & 1 || (k >> i) & 1) return false;
            if (i > 0 && ((j >> (i-1)) & 1)) return false;
            if (i < n-1 && ((j >> (i+1)) & 1)) return false;
        }
    }
    return true;
}

int main() {
    scanf("%d%d", &m, &n);
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < (1<<n); i++) {
        if (!(i & (i<<1))) {
            dp[1][i][0] = 1;
        }
    }
    for (int i = 2; i <= m; i++) {
        for (int j = 0; j < (1<<n); j++) {
            if (!(j & (j<<1))) {
                for (int k = 0; k < (1<<n); k++) {
                    if (!(k & (k<<1)) && !((j<<1) & k) && !(j & (k<<1))) {
                        for (int p = 0; p < (1<<n); p++) {
                            if (check(p, j, k)) {
                                dp[i][j][k] = (dp[i][j][k] + dp[i-1][k][p]) % MOD;
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < (1<<n); i++) {
        ans = (ans + dp[m][i][0]) % MOD;
    }
    printf("%d\n", ans);
    return 0;
}

其中，$dp[i][j][k]$ 表示在前 $i$ 行中，第 $i$ 行的状态为 $j$，第 $i-1$ 行的状态为 $k$ 的方案数。状态转移方程为：

$$dp[i][j][k] = \sum_{p=0}^{2^n-1} [check(p,j,k) = 1] dp[i-1][k][p]$$

其中，$check(p,j,k)$ 表示 $p$ 是否合法，即 $p$ 中每个格子都是 $1$ 的位置，$j$ 和 $k$ 中对应位置必须是 $0$，即不冲突。$2^n$ 表示每行格子数，$n$ 是矩阵的列数。

最终的答案就是 $dp[m][0][0]$，其中 $m$ 是矩阵的行数。