AcWing 1064. 小国王

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

输入格式
共一行，包含两个整数 n和 k

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

数据范围
1≤n≤10,0≤k≤n^2

3 2

16

#include<bits/stdc++.h>
using namespace std;

const int N=12,M= 1 << 10,K=110;
int n,m;
long long f[N][K][M];//已经摆好前n-1行 m个国王 第n行的状态是state(2进制）
vector<int> state;//每一行状态的二进制（合法
vector<int> head[M];//从某状态能转移到的状态 是二维数组
int cunt[M];//每个状态包含的1（国王数）

bool check(int state)//该行状态合法否 该行内部不能有2个1相邻
{
    return !(state & state >> 1);
}

int cnt(int state)//每个状态包含的1（国王数）
{
    int res=0;
    for(int i=0;i < n;i++) res += state >> i & 1;
    return res;
}

int main()
{
    cin>>n>>m;

    //预处理1 一个行可以有的所有状态
    for(int i=0;i< 1 << n;i++)
    {
        if( check (i))
        {
            state.push_back(i);//合法的放进去state
            cunt[i] = cnt(i);
        }
    }

    //预处理2 每个状态能转移到的其他状态
    for(int i=0 ;i < state.size() ;i++)
    {
        for(int j=0; j < state.size() ; j++)
        {
            int a=state[i],b=state[j];
            if( !(a & b) && check(a | b))//满足上下行不能相互攻击到
                head[a].push_back(b);
        }
    }

    f[0][0][0]=1;//这是一种方案数

    for(int i=1;i<=n  + 1; i++)//枚举行
    {
        for(int j=0 ; j <= m;j++)//枚举每个国王
        {
            for(auto a : state)//合理行的可能性
            {
                for(auto b : head[a])//该行能转移到的状态
                {
                    if( j >= cunt[a])
                        f[i][j][a] += f[i-1][j-cunt[a]][b];
                }
            }
        }
    }

    cout<<f[n+1][m][0]<<endl;

    return 0;
}