分析

f[i][j][z]为之前i-1行已摆好，摆在前i行，目前摆了j个国王，而且第i行的摆放状态为z的集合。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=12,M=(1<<10);
int n,k,idx,cnt[M],state[M];  
LL f[N][110][M];
bool st[M];
vector<int> head[M];
bool check(int x)   //找到一个状态(二进制数)中是否有相连的1
{
    for(int i=0;i<n-1;i++)
        if(((x>>i)&1) && ((x>>(i+1)) & 1)) return false;
    return true;
}
int count(int x)    //找到一个状态(二进制数)中1的个数
{
    int res=0;
    for(int i=0;i<n;i++) res+=(x>>i)&1;
    return res;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<(1<<n);i++)
    {
        if(check(i))    //计算当前状态是否为合法状态，
        {
            state[idx++]=i;   //是的话就加入到状态数组中
            cnt[i]=count(i);    //计算当前状态的1的个数(国王个数)
        }
    }
    for(int i=0;i<idx;i++)
    {
        for(int j=0;j<idx;j++)
        {
            int a=state[i],b=state[j];
            if((a&b)==0 && check(a|b))  //判断a、b两种合法状态能否进行转移
                head[i].push_back(j);
        }
    }

    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=0;j<=k;j++)
        {
            for(int z=0;z<idx;z++)
            {
                for(auto b:head[z])
                {
                    int c=cnt[state[z]];
                    if(j>=c)    //如果当前国王数比已经有的国王多，就加进去
                    {
                        f[i][j][state[z]]+=f[i-1][j-c][state[b]];
                    }
                }
            }
        }
    }
    cout<<f[n+1][k][0]<<endl;   //前n行已摆好，当前在n+1行，一共摆了k个国王，第n+1行状态为0的总方案数
    return 0;
}