第一种类型（摆放方块）：
代码如下：
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
using namespace std;
using ll = long long;
const int N = 15, M = 1 << N;
#define x first
#define y second
typedef pair<int, int> PII;
ll f[N][M], n, m;
bool st[M];
vector<int> state[M]; // 二维数组记录合法的状态
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
while (cin >> n >> m, n || m)
{ //读入n和m，并且不是两个0即合法输入就继续读入
//第一部分：预处理1
//对于每种状态，先预处理每列不能有奇数个连续的0
for(int i = 0; i < (1 << n); i ++)
{
int cnt = 0 ;//记录连续的0的个数
bool isValid = true; // 某种状态没有奇数个连续的0则标记为true
for(int j = 0; j < n; j ++)
{ //遍历这一列，从上到下，一列有n个数
if ( (i >> j) & 1)
{
//i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位；
// &1为判断该位是否为1，如果为1进入if
if (cnt & 1) // 二进制第0位是1就是奇数
{
//这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
isValid = false;
break;
}
cnt = 0; // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
//其实清不清零没有影响
}
else cnt ++; //否则的话该位还是0，则统计连续0的计数器++。
}
if (cnt & 1) isValid = false; // 最下面的那一段判断一下连续的0的个数，也就是说最下面有一段连续的0
st[i] = isValid; //状态i是否有奇数个连续的0的情况,输入到数组st中
}
// 第二部分：预处理2
// 经过上面每种状态 连续0的判断，已经筛掉一些状态。
//下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突
for (int j = 0; j < (1 << n); j ++)
{ // 对于第i列的所有状态
state[j].clear(); // 清空上次操作遗留的状态，防止影响本次状态。
for (int k = 0; k < (1 << n); k ++)
{ // 对于第i-1列所有状态
if ((j & k) == 0 && st[j | k])
// 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行)
// 解释一下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，即哪几行是横着放格子的
state[j].push_back(k);
//二维数组state[j]表示第j行，
//j表示 第i列“真正”可行的状态，
//如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
//“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
}
}
//第三部分：dp开始
memset(f, 0, sizeof f);
//全部初始化为0，因为是连续读入，这里是一个清空操作。
//类似上面的state[j].clear()
f[0][0] = 1 ;// 这里需要回忆状态表示的定义
//按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
//首先，这里没有-1列，最少也是0列。
//其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。
for (int i = 1; i <= m; i ++) { //遍历每一列:第i列合法范围是(0~m-1列)
for (int j = 0; j < (1<<n); j ++) { //遍历当前列（第i列）所有状态j
for (auto k : state[j]) // 遍历第i-1列的状态k，如果“真正”可行，就转移
f[i][j] += f[i-1][k]; // 当前列的方案数就等于之前的第i-1列所有状态k的累加。
}
}
//最后答案是什么呢？
//f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
//即整个棋盘处理完的方案数
cout << f[m][0] << endl;
}
return 0;
}
第二种类型（覆盖点）：
代码如下：
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
using namespace std;
using ll = long long;
const int N = 20, M = 1 << N;
#define x first
#define y second
typedef pair<int, int> PII;
ll f[M][N], n, m, weight[N][N];
bool st[M];
// 核心：
// 1. 哪些点被用过
// 2. 目前停在哪个点上
// 不同的状态数：2^20(20个点，用或不用，一维) * 20(二维) = 2 * 10^7
// f[state][j] = f[state_k][k] + weight[k][j]，state_k = state去掉j之后的集合，state_k要包含k
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 0; i < n ; ++i)
for (int j = 0; j < n; ++j)
cin >> weight[i][j];
memset(f, 0x3f, sizeof f);
f[1][0] = 0;// 初始化，初始状态state为1(第一个点)，目前停在0这个点上，走的路程为0
for (int i = 0; i < 1 << n ; ++i)
for (int j = 0; j < n; ++j)
{
if (i >> j & 1) // 判断是否合法
{
for (int k = 0; k < n; ++k)
{
//当前状态是i，想算k状态
if ((i - (1 << j)) >> k & 1)// 当前状态将第j位减去，因为k还没有走到j，最后判断合法性
{
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);
}
}
}
}
cout << f[(1 << n) - 1][n - 1];
return 0;
}
第三种类型（枚举合法方案数）：
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<tuple>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 110, mod = 1000000007, INF = 0x3f3f3f3f, M = 1 << 6, P = 13331, K = 21;
const double eps = 1e-8;
#define x first
#define y second
typedef pair<int, int> PII;
int T, n, m, k, len, res, e[M], ne[M], h[N], w[M], idx, dist[N], f[2][M][M][K], a[N];
bool st[M], flag;
int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
//int dx[9] = {-1, -1, -1, 0, 0, 1, 1, 1, 0}, dy[9] = {-1, 0, 1, -1, 1, -1, 0, 1, 0};
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
//priority_queue<PII, vector<PII>, greater<PII>> q[N];
vector<int> state;
ll cnt[M];
vector<int> head[M];
int get_count(int x) {
int res = 0;
while (x) {
++res;
x -= x & -x;
}
return res;
}
bool check1(int a, int b)
{
return !(b & (a >> 2) || a & (b >> 2));
}
bool check2(int a, int b)
{
return !(b & (a >> 1) || a & (b >> 1));
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
// 枚举同一行的合法状态
for (int st = 0; st < 1 << n; ++st) {
state.push_back(st), cnt[st] = get_count(st);
}
// 枚举相邻的两行的合法状态
for (auto st : state) {
for (auto ne_st: state) {
if (check1(st, ne_st)) {
head[st].push_back(ne_st);
}
}
}
// 初始化
// 考虑前i层，第i层状态为st 第i-1状态为p1 前i层放置了j个国王
f[0][0][0][0] = 1;
for (int i = 1; i <= m + 2; ++i) {
for (int j = 0; j <= k; ++j) {
for (auto &st : state) {
for (auto &p1 : head[st]) {
// 清空
// 这里就不需要保证第i行和i-1行是否合法了，因为取出的元素已经保证合法
f[i & 1][st][p1][j] = 0;
for (auto &p2 : head[p1]) {
// 保证第i-2行合法
if (check2(st, p2)) {
if (j - cnt[st] >= 0) {
f[i & 1][st][p1][j] = (f[i & 1][st][p1][j] + f[i - 1 & 1][p1][p2][j - cnt[st]]) % mod;
}
}
}
}
}
}
}
cout << f[m + 2 & 1][0][0][k] % mod;
return 0;
}
