基础的状压DP，因为是将状态压缩到一个整数中，所以会涉及到很多比较巧妙的位运算。
我们可以先把输入中每行的01压缩成一个整数。
判断一个状态是否有相邻1：
如果 x & (x << 1) 非0，说明有相邻的两个1
判断一个状态能否放在该行：
如果 (a[i] & state) != state，说明是不能放置的。因为a[i]中存在某个0和对应state中的1，与运算之后改变了state的值
判断相邻两行的状态是否有同一列相邻的1：
如果(state & _state)不为零，说明有相邻的1
#include <cstdio>
#include <cstring> const int maxn = ;
const int M = ;
int a[maxn], d[maxn][ << maxn];
int n, m, tot; inline bool check_row(int x) { return x & (x << ) ? false : true; } //判断一行是否有相邻的
inline bool check_col(int x1, int x2) { return x1 & x2 ? false : true; } //判断一列是否有相邻的
inline bool check_put(int a, int x) { return (x & a) == x ? true : false; } //判断该状态能否放在该行 int main()
{
//freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m) == )
{
memset(d, , sizeof(d));
for(int i = ; i < n; i++)
{
int t;
a[i] = ;
for(int j = ; j < m; j++) { scanf("%d", &t); a[i] = a[i] * + t; }
}
tot = ( << m);
for(int i = ; i < tot; i++) if(check_row(i) && check_put(a[], i)) d[][i] = ; for(int i = ; i < n; i++)
{//枚举行标
for(int state = ; state < tot; state++)
{//枚举该行的状态
if(!check_row(state) || !check_put(a[i], state)) continue;
for(int _state = ; _state < tot; _state++)
{//枚举上一行的状态
if(state & _state) continue;
d[i][state] = (d[i][state] + d[i-][_state]) % M;
}
}
} int ans = ;
for(int i = ; i < tot; i++) ans = (ans + d[n-][i]) % M;
printf("%d\n", ans);
} return ;
}
代码君