题意

一个 的方格，有的地方能放人，有的不能。人不能上下左右相邻放置。问放置方案总数。

题解

看到 这么小就知道是状压 DP。

以表示行的状态为例，设 为前 行处理完并且第 行的状态为 时的方案数目。那么只需要以行编号为阶段，内部枚举本行状态和上一行状态进行转移即可。

时间复杂度为 。

（注意非法状态的处理。）

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 100000000
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

int n, m, a[15][15], b[15] = {0};
int f[15][(1 << 13)];
void init(){
    memset(b, 0, sizeof(b));
    REP(i, 1, n){
        REP(j, 1, m){
            a[i][j] = read();
            if (!a[i][j]) b[i] |= (1 << j >> 1);
        }
    }
    memset(f, -1, sizeof(f));
    f[0][0] = 1;
}
void solve(){
    REP(i, 1, n){
        REP(j, 0, (1 << m) - 1){
            if (j & b[i]) continue;
            if (j & (j << 1)) continue;
            if (j & (j >> 1)) continue;
            REP(k, 0, (1 << m) - 1){
                if (f[i - 1][k] < 0) continue;
                if (k & j) continue;
                if (f[i][j] < 0) f[i][j] = 0;
                f[i][j] = modadd(f[i][j], f[i - 1][k]);
                // cout << i << " " << j << " " << f[i][j] << endl;
            }
        }
    }
    int ans = 0;
    REP(j, 0, (1 << m) - 1){
        if (f[n][j] >= 0) 
            ans = modadd(ans, f[n][j]);
    }
    printf("%d\n", ans);
}
int main(){
    while (scanf("%d%d", &n, &m) == 2){
        init();
        solve();
    }
    return 0;
}