试着写了一下非 dfs 版的，结果现在调不出来惹……

#include <bits/stdc++.h>
using namespace std;
#define MAXN 513

int n, k, tot, tmp;
int cnt[MAXN];
vector<int> ok;
long long ans;
long long f[10][82][MAXN];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;
    for (int i(0); i<(1<<n); ++i){
    	tot = 0;
    	tmp = i;
    	while (tmp){
    		if (tmp & 1) ++tot;
    		tmp >>= 1;
		}
		cnt[i] = tot;
		if (!(((i<<1)|(i>>1))&i)) ok.push_back(i);
	}
	
	f[0][0][0] = 1;
	for (int i(1); i<=n; ++i){
		for (int j: ok){
			for (int k: ok){
				if (!((k|(k<<1)|(k>>1))&j)){
					for (int l(cnt[j]); l<=k; ++l) f[i][l][j] += f[i-1][l-cnt[j]][k];
				}
			}
		}
	}
	
	for (int i: ok) ans += f[n][k][i];
	cout << ans;

    return 0;
}