洛谷P1896 互不侵犯

题目描述

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

输入格式

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出格式

所得的方案数

#include<bits/stdc++.h>
using namespace std;
int sat[2000], siz[2000];//sat 一行的合法状态 siz当前状态有多少个国王 
int cnt = 0;
int n, m;
long long f[10][2000][100] = {
     0 };//f[i][j][k]第i行 状态为j 放k个国王的方案数
void dfs(int Sta, int now_size, int i_th)//预处理出每一个状态 Sta 代表状态 00000 now_size代表当前已经有多少个国王 i_th代表当前是在用第几列的格子
{
    
    if (i_th >= n)//如果已经处理完毕（注意是大于等于）
    {
    
        sat[++cnt] = Sta;//处理第cnt个状态
        siz[cnt] = now_size;//第cnt个状态可以放国王的数量为 now_size个
        return;//新建一个状态
    }
    dfs(Sta, now_size, i_th + 1);//不用第i_th个格子
    dfs(Sta + (1 << i_th), now_size + 1, i_th + 2);//用第i_th个格子，此时i_th要加2，即为跳过下一个格子 因为左右不能相邻
}
int main()
{
    
    scanf("%d%d", &n, &m);
    dfs(0, 0, 0);
    for (int i = 1; i <= cnt; i++)f[1][i][siz[i]] = 1;//第一层的所有状态均是有1种情况的
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= cnt; j++)//上一层的状态为j
            for (int k = 1; k <= cnt; k++)//当前层的状态为k
            {
    
                if (sat[j] & sat[k])continue;//上下相临
                if ((sat[j] << 1) & sat[k])continue;//右上相邻
                if (sat[j] & (sat[k] << 1))continue;//左上相邻
                for (int s = m; s >= siz[j]; s--)f[i][j][s] += f[i - 1][k][s - siz[j]];//枚举s，计算f[i][j][s]
            }
    long long ans = 0;
    for (int i = 1; i <= cnt; i++)ans += f[n][i][m];//统计最终答案，记得用long long
    printf("%lld", ans);
    return 0;
}