原题
看取膜的数就知道暴搜死定，那么用状压，f[i][j]表示可以转移到i行j状态的方案数，和互不侵犯类似，但由于提前有赋值，所以把1和0换一下可以更方便的判断推导。
#include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int m,n; bool a[14][14];int b[14],f[14][9000]; int dfs(int x,int y,int zhuang,int net,int l,int old) { if(y>=n) { f[x+1][(net|b[x+1])]=(f[x+1][(net|b[x+1])]+old)0000000; return 0; } if(y-l>1&&((1<<y)&zhuang)==0) { int k=net; k=k|(1<<y); dfs(x,y+2,zhuang,k,y,old); } dfs(x,y+1,zhuang,net,l,old); } int main() { cin>>m>>n; for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) cin>>a[i][j]; for(int i=1;i<=m;++i) { b[i]=0; for(int j=1;j<=n;++j) { if(a[i][j]==1) a[i][j]=0; else a[i][j]=1; b[i]<<=1; b[i]+=a[i][j]; } } f[1][b[1]]=1; //从f【0】【0】推也可以 for(int i=1;i<=m;++i) for(int j=0;j<(1<<n);++j) if(f[i][j]) { dfs(i,0,j,0,-2,f[i][j]); } int ans=0; for(int i=0;i<(1<<n);++i) ans=(ans+f[m+1][i])0000000; cout<<ans; return 0; }
