算法思想
核心
- 先放横着的再放竖着的
- 总方案数 = 只放横着的方块的合法方案数
- 每一列内部所有连续的空格子数为偶数个
状态表示
f[i][j]
表示前0 ~ i-1
列已经摆好,且从i-1
列伸到i
列,当前i列的状态是j的所有方案数
状态计算
转移条件:
1. 状态j和k(j的前一列)不能在同一行向右伸出,即j&k == 0
2. 所有空格子的位置的长度必须是偶数,即st[j | k] == true
当前列状态的合法数 = 前一列合法数在满足转移条件下的和
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N;//M的每一位二进制位储存一种状态
int n, m;
long long f[N][M];
bool st[M];//储存每一列上合法的摆放状态
//f[i][j]表示摆放第i列,第i-1列向后伸出来横着的方格状态为j(当前状态),的方案数,j为一个二进制数,用01表示
int main()
{
while (cin >> n >> m, n || m)
{
//一共n行,每行占一位,枚举所有状态是否合法
//(0代表第一行为空,1代表第一行不空,2 = 10代表第二行不空,3 = 11代表第一、二都不空)
for (int i = 0; i < 1 << n; i ++ )
{
int cnt = 0;//用来记录当前列空格子的个数
st[i] = true;//记录这个状态被枚举过且可行
for (int j = n - 1; j >= 0; j -- )//枚举当前列的每一行,即从低位到高位枚举它的每一位
if (i >> j & 1)//如果当前行(j从n-1开始,当前行即第0行)不空
{
//当前行不空,代表该行以上应能插入竖方块,所以空格子数应为偶数
if (cnt & 1) //如果当前列空格子的个数是奇数,竖方块插不进来
{
st[i] = false;
break; //跳出行循环,继续下一种状态是否合法
}
}
else cnt ++ ;//当前行为空,记录空格子数,计数器+1
if (cnt & 1) st[i] = false;//该列总空格数是否为奇数
}
memset(f, 0, sizeof f);//一定要记得初始化成0,对于每个新的输入要重新计算f[N][M]
f[0][0] = 1;
for (int i = 1; i <= m; i ++ )//对于每一列,第0列已经摆好
for (int j = 0; j < 1 << n; j ++ )//枚举该列的所有状态(被插状态,前一列伸到当前列)
for (int k = 0; k < 1 << n; k ++ )//再枚举前一列的伸出状态k(被插状态)
if ((j & k) == 0 && st[j | k])//如果i-1这一列没有冲突,被占位的情况也是合法的话
f[i][j] += f[i - 1][k];//那么这种状态下它的方案数等于之前每种k状态数目的和
cout << f[m][0] << endl;//求的是第m-1列排满,并且第m-1列不向外伸出块的情况
//0~m-1是题目中可以摆方块的范围
}
return 0;
}