算法

(状压dp)

直接上代码，注解在代码里
有些的不清晰的地方还望各位大佬见谅

C++ 代码

//状态压缩dp
//https://www.acwing.com/problem/content/293/
//本题状态压缩dp的技巧在于用2进制数表示每列格子的状态 
//这道题我们只需要排好横向的块，再把竖向的块的合法性判断好就可以了 

#include <bits/stdc++.h>

using namespace std;

const int N = 12;
const int M = 1 << N;                            

int n, m;
long long f[N][M];                                  //N表示的是列数，M表示的是该列数上块的状态 
bool st[M];                                         //用于记录某个状态下竖着放是否合法 

int main()
{
    while(cin >> n >> m, n || m)
    {
        //这里竖着放合法的状态就是该状态下不存在连续奇数个0，即不存在连续的奇数个空位 
        for(int i = 0; i < 1 << n; i++)             //预处理出竖着放合法的状态 
        {
            st[i] = true;
            int cnt = 0;                            //计时器记录连续的0的个数 
            for(int j = 0; j < n; j++)
                if(i >> j & 1)                      //判断第i位上是否放有方块 
                {
                    if(cnt & 1)                     //有的话就判断一下，如果cnt为奇数就证明存在连续个奇数 
                        st[i] = false;              //判断出这个状态不合法 

                    cnt = 0;                        //判断完后重置计数器，重新开始计算连续0的个数 
                }
                else
                    cnt++;

            if(cnt & 1)                             //到末尾再判断一下前面0的个数是否为奇数 
                st[i] = false;
        }

        memset(f, 0, sizeof f);                     //重置f状态 
        f[0][0] = 1;                                //预处理f[0][0] 
        for(int i = 1; i <= m; i ++)                //m是不存在的1行，是为了方便最后状态顺利转移成能导出的答案 
            for(int j = 0; j < 1 << n; j++)         //枚举第i行的状态 
                for(int k = 0; k < 1 << n; k++)     //枚举第i - 1行的状态 
                    if((j & k) == 0 && st[j | k])   //(j & k) == 0表示没有两个横着放的方块重叠，
                        f[i][j] += f[i - 1][k];     
                        //st[j | k]表示竖着放在这个状态下是合法的，j | k出的状态就是我们之前在预处理的状态 

        cout << f[m][0] << endl;                
        //输出第m行且一个方块都没摆的状态，也就是m行不存在的状态，也就是我们图原本的样子 
    }

    return 0;
}