在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。

方案数。

3 2

16

题目分析：

状压DP dp[i][j][k]代表第i行 数量为j时 状态为k 的方案数

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
bool map[110][110];
int check(int x)
{
    if(x&(x<<1)||x&(x>>1))
        return 0;
    int cnt=0;
    while(x)
    {
        x=x&(x-1);
        cnt++;
    }
    if(cnt>m) return 0;
    return 1;
}
int getnum(int x)
{
    int cnt=0;
    while(x)
    {
        x=x&(x-1);
        cnt++;
    }
    return cnt;
}
int num[110];
int stay[110];
long long dp[10][110][110];
long long ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<(1<<n);i++)
        if(check(i))
            num[++num[0]]=getnum(i),stay[++stay[0]]=i;
    for(int i=1;i<=num[0];i++)
        for(int j=1;j<=num[0];j++)
            if(!(stay[i]&stay[j])&&!((stay[i]>>1)&stay[j])&&!((stay[i]<<1)&stay[j]))
                map[i][j]=true;
    for(int i=1;i<=num[0];i++)
        dp[1][num[i]][i]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=1;k<=num[0];k++)
            {
                if(num[k]>j) continue;
                for(int l=1;l<=num[0];l++)
                    if(map[k][l]&&num[k]+num[l]<=j)
                        dp[i][j][k]+=dp[i-1][j-num[k]][l];
            }
    for (int i=1;i<=num[0];i++) ans+=dp[n][m][i];
    printf("%lld",ans);
    return 0;
}