题目

求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。

例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。

如下图所示：

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数 N 和 M。

当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

1≤N,M≤11

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

思路

 

代码

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
vector<int> state[M];//存可以到达的状态
bool st[M];//所有连续空格是复数的为true 

int main()
{
	while(cin >> n >> m, n || m)
	{
		for(int i = 0; i < 1 << n; i ++)//遍历所有状态，是否连续空格全为复数 
		{
			int cnt = 0;
			bool is_valid = true;
			for(int j = 0; j < n; j ++)
				if(i >> j & 1)//遇到1时 
				{
					if(cnt & 1)//奇数 
					{
						is_valid = false;
						break;
					}
					cnt = 0;//下个连续的0 清空 
				}
				else cnt ++;
			if(cnt & 1) is_valid = false;//最后一个 
			st[i] = is_valid;
		}	
		
		for(int i = 0; i < 1 << n; i ++)//初始化state 存储所有能从j 到 i 的数据 
		{
			state[i].clear();
			for(int j = 0; j < 1 << n; j ++)
				if((i & j) == 0 && st[i | j])//无重叠 + 连续空格全为复数 
					state[i].push_back(j);
		}
		
		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(auto k : state[j])
					f[i][j] += f[i - 1][k];
		
		cout << f[m][0] << endl;
		
	} 
	return 0;
}