题目描述
n×m的棋盘可以摆放不同的1×2小方格的种类数。
算法1
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N =12,M = 1<<N;
long long f[N][M];
bool st[M];//表示当前状态j中连续的0的个数是奇数还是偶数
int main()
{
int n,m;
while(cin >>n >>m, n||m)
{
//预处理一下列中的所有状态0~ (1<<n)-1
for(int i= 0;i < 1<<n;++i)
{
int cnt =0;// count 0
st[i] = true;
for(int j=0;j<n;++j)
{
if(i>>j & 1)
{
if(cnt & 1) st[i] = false; //判断cnt的最后一位是否为1
cnt =0;
}
else cnt ++;
}
if(cnt & 1) st[i] = false;
}
memset(f,0,sizeof(f));//每种输入初始化一下
f[0][0] = 1;//初始化,第0列只能竖着摆有几种情况,那肯定只有一种
for(int i=1;i<=m;++i)
{
for(int j=0;j<1<<n;++j)
{
for(int k=0;k< 1<<n;++k)
{
//根据当前列的状态和上一列的状态,判断状态是否可以转移
//1. j&k == 0 ,这一步比较好理解,就是说当前列
//只能在上一列没有伸出的方块的地方放置方块
//2. j|k ,之所以两个状态相与,是因为上一列中有方块
//伸到当前列,要把这一个地方置为1,表示已经有方块了
if((j&k) ==0 && st[j|k])
f[i][j] += f[i-1][k];
}
}
}
cout << f[m][0]<<endl;
}
}
解释一:(j&k) ==0
看一下图更好理解,上图假设上一列k=0011
,那当前列有两种取法j=1111 和 j=0011
。(j&k) == 0
的意思就是,当前列只能在上一列没有伸出方块的地方放置横向方块。
解释二:j|k
还是看一下图。之所以两个状态相与,是因为上一列中有方块伸到当前列,要把这一个地方置为1,表示已经有方块了