1. 题目

传送门＝￣ω￣＝

2. 题解

这题一看就可以状压。
可以一个格子一个格子地搜索，记录上一行的状态。
我的做法是先预处理出一行中可能的所有状态（即这一行上的国王都不会互相攻击），再在动归过程中枚举这一行的状态，与上一行比较，这样一整行一整行地搜，理论上会快一点吧。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,st[300],stc,f[10][100][1000],ans;
void initdfs(int c,int k)
{
    if(c>n){st[stc++]=k;return;}
    initdfs(c+1,k);
    if(!(k&(1<<(c-1))))initdfs(c+1,k|(1<<c));
}
int dfs(int c,int l,int k)//当前搜到了第 c 行，放了 l 个棋子，上一行状态为 k
{
    for(int i=1;i<=n;i++)l+=((k>>i)&1);
    if(f[c][l][k]!=-1)return f[c][l][k];
    if(l==m)return f[c][l][k]=1;
    if(c>n||l>m)return f[c][l][k]=0;
    f[c][l][k]=0;
    for(int i=0;i<stc;i++)
        if(!(k&st[i])&&!((k<<1)&st[i])&&!((k>>1)&st[i]))
            f[c][l][k]+=dfs(c+1,l,st[i]);
    return f[c][l][k];
}
int main()
{
    scanf("%d%d",&n,&m),initdfs(1,0),memset(f,-1,sizeof(f));
    printf("%d\n",dfs(1,0,0));
    return 0;
}