题目描述

这道题目总体还是容易理解的，关键的地方在于转换思路，求横着放的方块放满之后，剩下的是否满足情况。
从f[0][0]开始判断，f[0][0]只有两种情况 0 ，1，当行数位偶数时为1，行数为奇数时为0；

f[i - 1][j] 表示 第i - 1 列第j种情况下有多少种可能（注意这里是使用j来表示第多少种情况，加入有n行，那么就可能将j看作n位二进制数字，然后为1就表示为当前方格放了一个横的，为0表示当前方格没有放横的）

在求f[i][j]的时候就会有两种情况
（1）j & K != 0 ，表明i - 1 列这里已经已经放了横的，第i列一定放不下一个1*2的横的
（2）st[j | k] (j表示第i列的第j种情况，k表示第i - 1列的第j种情况) j | k 表示不可以放横着放的剩下的连续0（要放竖着的）的情况，若连续0个数为偶数，则说明可以，为奇数说明不可以。

C++ 代码

#include <iostream>
#include <limits.h>
#include <cstring>
using namespace std;
const int N = 12 , M = 1 << N;

long long f[N][M];
bool st[M];

int main(){
    int n , m;
    while(cin >> n >> m , n || m){
        memset(f , 0 , sizeof f);
        for(int i = 0;i < 1 << n;++i){
            int cnt = 0;
            st[i] = true;
            for(int j = 0;j < n;++j){
                if(i >> j & 1){
                    if(cnt & 1 ) st[i] = false;
                     cnt = 0;
                }else ++ cnt;
            }
            if(cnt & 1)st[i] = false;
        }
        f[0][0] = 1; // 第0列横着的有多少个
        for(int i = 1;i <= m;++i){
            for(int j = 0;j < 1 << n;++j){
                for(int k = 0;k < 1 << n;++k){
                    if((j & k) == 0 && st[j |k]) f[i][j]  += f[i - 1][k]; 
                }
            }
        }
        cout << f[m][0] << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla