C++

$\color{#cc33ff}{— > 算法基础课题解}$

时间复杂度：$O(2 ^ {2n} * n)$

#include<iostream>
#include<algorithm>
#include <cstring>

using namespace std;

const int N = 15, M = 1 << N;

int n, m;
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 ++) {
            st[i] = true;
            int cnt = 0;
            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;
        for (int i = 1; i <= m; i ++) // 枚举所有的列
            for (int j = 0; j < 1 << n; j ++) // 枚举所有的状态
                for (int k = 0; k < 1 << n; k ++) // 枚举 i - 1 列的所有状态
                    if((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];

        cout << f[m][0] << endl;         
    }
    return 0;
}