每一行 伸出来为1 没伸为0
i=2 j=11001 ——>用一个状态表示一类方案【化零为整】
k 看的是从i-2伸到i-1 共有2^n种方案 可以遍历f(i,j)的全部情况【化整为零】判断是否满足题意:
(1)j和k不能在同一行都是1 会有重复——j&k==0m为总列数 f[m,0] 恰好表示了摆满n×m棋盘的状态
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=12,M=1<<N;//N为列数 M为所有方案数(2^N)
long long f[N][M];
bool st[N];//st存是否满足所有连续空位置必须是偶数
int main(){
int n,m;
while(cin>>n>>m ,n||m ){
for(int i=0;i<1<<n;i++){
st[i]=true;
int cnt=0;
for(int j=0;j<n;j++){
if(i>>j&1){ //说明上面的一堆0结束了
if(cnt&1) st[i]=false;
cnt=0;
}
else cnt++;
}
if(cnt&1) st[i]=false;
}
memset(f,0,sizeof f);
f[0][0]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<1<<n;j++){
for(int k=0;k<1<<n;k++){
if((j&k)==0 && st[j|k]){
f[i][j]+=f[i-1][k];
}
}
}
}
cout<<f[m][0]<<endl;
}
return 0;
}