在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。

输入格式

共一行，包含两个整数 n 和 k。

输出格式

共一行，表示方案总数，若不能够放置则输出0。

数据范围

1≤n≤10,
0≤k≤n^2

输入样例：

3 2

输出样例：

16

思路：

f[i][j][k]:表示前i行放置了j个国王，且第i行的状态是k        属性:cnt

首先考虑当前这一行，找到当前这一行所有的合法状态（即状态的纵坐标不相邻），以及合法状态的合法转移状态（因为当前这一行的状态肯定是上一行转移过来的，所以只需要考虑上一行的状态。 那么上一行什么样的状态才能转移成当前的状态？由题意发现上一行状态与当前行状态的纵坐标不能相邻，上下不能相邻，左右也不能相邻）以便于状态转移计算。

状态表示：

f[i][j][k]:表示前i行放置了j个国王，且第i行的状态是k        

属性:cnt

状态计算：

f[i][j][k] +=  f[i-1][j-cnt[state]][state]

初始状态：

f[0][0][0]

目标状态：

f[n+1][k][0]        

因为只要这层不摆东西，则上一层 只要合法，那一定可以转移到这一层的这个0状态

解决代码：

#include
#include
#include
#include
#include
using namespace std;typedef long long LL;const int N = 11, M = 1 << N, C = N * N;int n, m, k;
LL f[N][C][M];			//f[i][j][k]:表示前i行放置了j个国王，且第i行的状态是k		属性:cnt 
int cnt[M];			//用来存储每个合法状态中有多少个国王 
vector legal;		//存放合法状态数组 
vector trans[M];	//存放合法状态的合法转移状态 bool check(int state)		//检查纵坐标是否相邻 
{return !(state&state>>1);
}int count(int state)	
{int cnt = 0;for(int i=0;i>i&1) cnt++;return cnt;
}int main()
{cin>>n>>k;//预处理所有状态for(int i=0;i<1<=0)f[i][j][st] += f[i-1][j-cnt[st]][tt];LL ans = 0;			for(auto s : legal)ans += f[n][k][s];cout<