include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 12, M = 1 << N;//表示2的n次方
int n, m;
long long dp[N][M];//二维表示状态
bool st[N];//判断该列空着的位置是否为偶数
int main()
{
//输出n,m,且保证n,m均不为0方可进入循环
while (cin >> n >> m, n || m)
{
//部分I:预处理1
//这里循环的是不同的状态,应该这样理解,比如i = 1(假如n = 3),指的是001,也就是只有最后行放了横向方块的方案
//那么以每个状态为基点开始,遍历每个状态下的情况
for (int i = 0; i < 1 << n; i)
{
bool is_valid = true;
int cnt = 0;//cnt表示一列中0的个数
//第i列下每个数字是否放置,也就是统计以下0的个数
for (int j = 0; j < n; j)
{
if (i >> j & 1)//检查该方案下的第j行是否为1
{
//若这一位为1,那就要看前面连续的0的个数,如果是奇数(cnt &1为真)则该状态不合法,cnt为偶数,cnt&1则为0!!
//这里是判断连续的0,故而是要判断多次的,每次的1前面都可能出现不同情况的0
if (cnt & 1)
{
is_valid = false;
break;
}
}
else//若不是1,那就是0
cnt++;
}
if (cnt & 1) is_valid = false;
st[i] = is_valid;//记录每个状态i的合法性
}
//部分II:dp
// 经过上面每种状态 连续0的判断,已经筛掉一些状态。
//下面来看进一步的判断:看第i-2列伸出来的和第i-1列伸出去的是否冲突,如果没有,直接进行状态转移
//棋盘是从第0列开始,没有 - 1列,所以第0列第0行,不会有延伸出来的小方块
//没有横着摆放的小方块,所有小方块都是竖着摆放的,这种状态记录为一种方案
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
//遍历每一列,开始进行状态转移
for (int i = 1; i <= m; i++)
{
//第i列的不同情况
for (int j = 0; j < 1 << n; j++)//对于第i列的所有状态
{
//第i-1列不同的情况
for (int k = 0; k < 1 << n; k++)//对于第i-1列所有状态
{
if ((j & k) == 0 && st[j | k])
//第i - 2列伸出来的和第i - 1列伸出来的不冲突(不在同一行)与j,k合并后该列的放置横格子的情况
//解释一下st[j | k]
//已经知道st[]数组表示的是这一列没有连续奇数个0的情况,
//我们要考虑的是第i-1列(第i-1列是这里的主体)中从第i-2列横插过来的,
//还要考虑自己这一列(i-1列)横插到第i列的
//比如 第i-2列插过来的是k=10101,第i-1列插出去到第i列的是 j =01000,
//那么合在第i-1列,到底有多少个1呢?
//自然想到的就是这两个操作共同的结果:两个状态或。 j | k = 01000 | 10101 = 11101
//这个 j|k 就是当前 第i-1列的到底有几个1,即哪几行是横着放格子的
dp[i][j] += dp[i - 1][k];
}
}
}
//棋盘一共有0~m-1列
//f[i][j]表示 前i-1列的方案数已经确定,从i-1列伸出,并且第i列的状态是j的所有方案数
//f[m][0]表示 前m-1列的方案数已经确定,从m-1列伸出,并且第m列的状态是0的所有方案数
//也就是m列不放小方格,前m-1列已经完全摆放好并且不伸出来的状态
cout << dp[m][0] << endl;
}
return 0;
}