可结合 P10482 Sudoku 2 加强对状压的理解。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// 不会太多，n=10时算了下有144个
const int MAXS = 200, MAXN = 12;
// f[i][j][k]：从第一行到第i行、共放置了k个国王、
// 第i行的状态是j的方案数。
LL f[MAXN][MAXS][MAXN * MAXN];
int s[MAXS], tot; // 预处理一行的有效状态。
int cnt[MAXS]; // 预处理一个有效状态所含1的个数

int main() {
	int n, k;
	cin >> n >> k;

	int U = (1 << n) - 1;
	for (int i = 0; i <= U; i++) {
		if (( ( (i << 1) | (i >> 1) ) & i) == 0) {
			s[++tot] = i;
			cnt[tot] = __builtin_popcount(i);
//			cout << i << ' ' << __builtin_popcount(i) << '\n';
			f[1][tot][cnt[tot]] = 1;
		}
	}
//	cout << "dbg" << tot << '\n';

	// 枚举当前放到第几行row
	for (int i = 2; i <= n; i++) {
		// 枚举每个可行的行row状态
		for (int now = 1; now <= tot; now++)
			// 遍历上一行的所有状态，统计哪些不会与现在行row的状态冲突
			for (int pre = 1; pre <= tot; pre++) {
				if (((s[now] | (s[now] << 1) | (s[now] >> 1)) & s[pre]) == 0) {
					// 枚举剩余国王个数
					for (int j = cnt[now]; j <= k; j++)
						f[i][now][j] += f[i - 1][pre][j - cnt[now]];
				}
			}
	}

	LL ans = 0;
	for (int i = 1; i <= tot; i++) ans += f[n][i][k];
	cout << ans;

	return 0;
}

纯搜 From HYR，45分其他点全部TLE。

#include<iostream>
using namespace std;
int n,m;
bool a[20][20];
long long dfs(int i,int j,int k){
	if(k==m){
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=n;j++)
//				cout<<a[i][j]<<" ";
//			cout<<"\n";
//		}
//		cout<<"\n";
		return 1;
	}
	if(j>n)
		return dfs(i+1,1,k);
	if(i>n)
		return 0;
	long long ret=0;
	if(!a[i-1][j]&&!a[i-1][j-1]&&!a[i][j-1]&&!a[i-1][j+1]){
		a[i][j]=true;
		ret+=dfs(i,j+1,k+1);
		a[i][j]=false;
	}
	return ret+dfs(i,j+1,k);
}
int main(){
	cin>>n>>m;
	cout<<dfs(1,1,0);
	return 0;
}