题目描述
把 N×M
的棋盘分割成若干个 1×2
的长方形,有多少种方案。
例如当 N=2,M=4
时,共有 5
种方案。当 N=2,M=3
时,共有 3
种方案。
如下图所示:
2411_1.jpg
输入格式
输入包含多组测试用例。
每组测试用例占一行,包含两个整数 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
(暴力枚举) $O(n^2)$
C++ 代码
#include <cstring> // 引入头文件cstring,用于memset函数
#include <iostream> // 引入头文件iostream,用于输入输出流
#include <algorithm> // 引入头文件algorithm,用于一些算法函数
using namespace std; // 使用标准命名空间
const int N = 12, M = 1 << N; // 定义常量N为12,M为2的N次方
int n, m; // 定义变量n、m
long long f[N][M]; // 定义二维数组f,大小为N行M列,用于动态规划
bool st[M]; // 定义布尔数组st,大小为M,用于判断每种情况是否可行
int main()
{
while (cin >> n >> m, n || m) // 当输入n或m不为0时循环执行
{
for (int i = 0; i < (1 << n); i ++ ) // 枚举每一种情况
{
int cnt = 0; // 计数器,用于统计连续0的个数
st[i] = true; // 初始化当前情况为可行
for (int j = 0; j < n; j ++ ) // 遍历n位
if (i >> j & 1) // 如果第j位为1
{
if (cnt & 1) st[i] = false; // 如果连续0的个数为奇数,则当前情况不可行
cnt = 0; // 重置连续0的个数
}
else cnt ++ ; // 如果第j位为0,连续0的个数加1
if (cnt & 1) st[i] = false; // 如果最后一位是0,说明连续0的个数为奇数,当前情况不可行
}
memset(f, 0, sizeof f); // 将动态规划数组f全部初始化为0
f[0][0] = 1; // 初始状态为第0行第0列的情况为1
for (int i = 1; i <= m; i ++ ) // 从第1行开始遍历到第m行
for (int j = 0; j < (1 << n); j ++ ) // 枚举所有的状态
for (int k = 0; k < (1 << n); k ++ ) // 枚举上一行的状态
if ((j & k) == 0 && st[j | k]) // 如果当前状态和上一行状态的交集为0,并且合并后的状态是可行的
f[i][j] += f[i - 1][k]; // 更新动态规划数组f的值
cout << f[m][0] << endl; // 输出结果
}
return 0; // 返回0,表示程序正常结束
}
手写题解