解法： 核心：先放横着的，再放竖着的。
总方案数，等于只放横着的小方块的合法方案数。 如何判断当前方案是否合法？所有剩余位置，能否填充满竖着的小方块。 即按列来看，每一列内部所有连续的空着的小方块，是偶数个。
动态规划思路： 状态表示：f[i,j]表示已经将前i-1列摆好，且从第i-1列，伸出到第i列的状态是j的所有方案。
状态计算：f[i,j] = ∑f[i-1,k]，f[i-1,k]指的是可以到达f[i,j]的合法f[i-1]的状态。
结果状态：f[m,0]，即前m列已经被铺满，m+1列一个格子都没有被占，即m列中没有伸到m+1列的小方块的状态。
状态转移图解：
有了思路，就可以开始解题了。
先求得一个状态是否是合法状态。
// i是状态压缩以后的十进制数
// n是状态位最大值
// 这个方法是求00000到11111这些状态是否合法（状态的长度是n）
bool isValid(int i, int n) {int cnt = 0;for (int j = 0; j < n; j++) {// 遍历状态i的每一个位数，以确定这个状态是不是合法的，检查方法就是数里面连续0的个数是不是偶数if ((i >> j) & 1) { // i的第j位是不是1// 如果是1，则查看之前已经有多少个0了，0的个数是不是偶数// 如果是偶数，则无妨，如果是奇数，则说明该状态位为非法if (cnt & 1) { // 使用位运算判断奇偶return false;}}}return true;
}根据上面的分析可以得到，一个合法的状态j，可以由很多个其他的合法状态转移而来，现在把每个合法的状态j的前一个合法状态集合求出来。
// 所有合法状态的前一个合法状态集合（可以到达i,j状态的状态）for(int j = 0; j < 1 << n; j++ ){state[j].clear(); // 暂时不用管这个是什么for(int k = 0; k < 1 << n; k++){if((j & k) == 0 && st[j | k] ){ // st中存储了所有状态是否合法（上面方法算出来的存到这里面）state[j].push_back(k);}}}
dp就比较简单了：
这样一来，全部的代码如下：
#include<iostream>
#include<cstring>
#include<vector>using namespace std;
typedef long long LL;const int N = 12;
const int M = 1 << N;int st[M]; // 1合法，0不合法
vector<int> state[M]; // [j]表示，可以转移到状态j的合法状态集合
int n,m;
LL f[N][M];
int main(){while(cin >> n >> m, n || m){// 求的所有合法的st[i]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){if(cnt & 1) {st[i] = 0;is_valid = false;break;}cnt = 0;}else{cnt++;}}if(cnt & 1) is_valid = false;st[i] = is_valid;}// 所有合法状态的前一个合法状态集合（可以到达i,j状态的状态）for(int j = 0; j < 1 << n; j++ ){state[j].clear();for(int k = 0; k < 1 << n; k++){if((j & k) == 0 && st[j | k] ){state[j].push_back(k);}}}// 动态规划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;
}
