题目大意：
已知一个01矩阵，其中为1的点可以取，并且取了的点不能相邻（上下左右四个方向），问有多少种取点方案
思路：
状压dp
把每行能取的状态记为二进制的数，则dp(i,j)表示第i行，状态为j的方案数
但是同时需要一些小技巧，①判断是否与原图相符 ②自己是否有相邻的 ③与上一行是否有相邻的
对于②，需要&一下该状态和该状态左移一位，若不为0则不符合题意
对于①和③，先把题中的方案全部取反，然后&一下该状态和它所在行数的状态，若不为0则不符合题意
完事
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<queue> #include<vector> #define ll long long #define inf 2147483611 #define MAXN 20101 #define mod 100000000 using namespace std; inline int read() { int x=0,f=1; char ch;ch=getchar(); while(ch<'0'&&ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,dp[17][MAXN],a[MAXN]; int x,r[17],k; bool j1(int x) {return (x&(x<<1));} bool j2(int x,int e) {return (a[x]&r[e]);} int main() { n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { x=read(); if(x==0) r[i]+=(1<<(m-j)); } for(int i=0;i<(1<<m);i++) if(!j1(i)) a[k++]=i; for(int i=0;i<k;i++) { if(!j2(i,1)) dp[1][i]=1; } for(int i=2;i<=n;i++) { for(int j=0;j<k;j++) { if(j2(j,i)) continue; for(int l=0;l<k;l++) { if(j2(l,i-1)) continue; if(!(a[l]&a[j])) dp[i][j]+=dp[i-1][l]; } } } int ans=0; for(int i=0;i<k;i++) {ans+=dp[n][i];ans%=mod;} printf("%d",ans); }