题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
输入输出格式
输入格式：
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出格式：
所得的方案数
输入输出样例
输入样例#1：
3 2
输出样例#1：
16
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,k,i,j,w,m;//n*n的棋盘k个国王
int t[];
int f[][][];//f[i][j][k]表示i行j状态放置k个国王的方案数
int check(int x,int y)//x在上，y在下 ,1为满足条件，0为不满足条件
{
if ((x&y)!=) return ;//如果x和y中有上下都是1情况，返回0；
if ((x&(x<<))>) return ;//如果x转成二进制后有相邻的1返回0；
if ((y&(y<<))>) return ; //如果y转成二进制后有相邻的1返回0；
if ((y&(x<<))>) return ;//如果x与y的左下方有冲突，返回0；
if ((x&(y<<))>) return ;//如果x与y的右下方有冲突，返回0；
return ;//否则就返回1
}
int main()
{
cin>>n>>k;
m=(<<n)-;//2^k-1
for (i=;i<=m;i++)//求t数组
t[i]=t[i>>]+(i&);//将i转成2进制后1的个数，为何要用位运算：省时间！
f[][][]=;//初始值
for (i=;i<=n;i++)//枚举行
for (j=;j<=m;j++)//枚举本行状态
for (w=;w<=m;w++)//枚举上一行状态
if (check(w,j)==)//如果这种放置方法合法
{
for (int kkk=t[j]+t[w];kkk<=k;kkk++)//t[j]+t[w]为这两行的国王数，k为一共放置的国王数
f[i][j][kkk]=f[i][j][kkk]+f[i-][w][kkk-t[j]/*减去本行国王数之后剩下的*/];//加进去
}
int sum=;
for (i=;i<=m;i++)
sum+=f[n][i][k];//统计
printf("%d",sum);//输出
return ;
}