说一下我的思路：
$f_{i,j,k}$ 表示第 $i$ 行状态为 $j$ 前面已经放了 $k$ 个国王。
$\mathop{f_{i,j,k}}\limits_{valid(j)}=\sum \mathop{f_{i-1,l,k-cnt(l)}}\limits_{valid(l),nd(j,l)}$
$cnt(x)$ 表示二进制下 $x$ 有几个 1，$valid(x)$ 表示某一行的状态是合法的，$nd(x,y)$ 表示作为上下两行的状态 $x$ 和 $y$ 并不冲突。
不知道哪里错了，样例也过不了。
求助qaq

#include<bits/stdc++.h>
using namespace std;
int n,K;
long long f[12][4096][12];
inline bool valid(int x){
	if(x&(x>>1)) return 0;
	if(x&(x<<1)) return 0;
	return 1;
}
inline bool nd(int x,int y){
	if(x&(y<<1)) return 0;
	if(x&y) return 0;
	if(x&(y>>1)) return 0;
	return 1;
}
inline int cnt(int x){
	int tmp=0;
	while(x){
		if(x&1) ++tmp;
		x>>=1;
	}
	return tmp;
}
int main(){
	cin>>n>>K;
	for(int j=0;j<(1<<n);++j)
	 if(cnt(j)<=K&&valid(j))
	  f[1][j][cnt(j)]=1;
	for(int i=2;i<=n;++i)
	 for(int j=0;j<(1<<n);++j)
	  if(valid(j))
	   for(int k=0;k<=K;++k)
	    for(int l=0;l<(1<<n);++l)
	     if(valid(l))
	      if(nd(j,l))
	       f[i][j][k]=f[i][j][k]+f[i-1][l][k-cnt(l)];
    long long ans=0;
    for(int j=0;j<(1<<n);++j)
     if(valid(j))
      ans=ans+f[n][j][K-cnt(j)];
    cout<<ans<<endl;
    return 0;
}