题目描述
在 n×n
的棋盘上放 k
个国王,国王可攻击相邻的 8
个格子,求使它们无法互相攻击的方案总数。
输入格式
共一行,包含两个整数 n
和 k
。
输出格式
共一行,表示方案总数,若不能够放置则输出0
。
数据范围
1≤n≤10
,
0≤k≤n2
样例
3 2
算法
思路:蒙德里安+棋盘
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 11, M = 1 << N;
long long int f[N][M][N * N]; //f[i][j][k]表示第i行第j种状态包含k个棋子,的方案数
bool str[M]; //判断状态是否合法
int lowbit(int x) //返回1的个数
{
int res = 0;
while(x)
{
x -= (x & -x);
res ++;
}
return res;
}
int main()
{
int n, k;
scanf("%d%d", &n, &k);
for(int t = 0; t < 1 << n; t ++)
if(lowbit(t) <= k && !(((t >> 1) & t) || ((t << 1) & t))) //判断状态是否合法
str[t] = true;
f[0][0][0] = 1; //第0行状态是0有0个棋子的方案数是1
for(int t = 1; t < 1 << n; t ++)
if(str[t])f[0][t][lowbit(t)] ++; //表示第0行的状态方案数
for(int i = 1; i <= n; i ++) //从第1行开始枚举
for(int j = 0; j < 1 << n; j ++) //枚举第i行的所有状态
if(str[j]) //合法就继续
for(int t = 0; t < 1 << n; t ++) //枚举第i-1行的所有状态
if(str[t] && !(j & t || (j >> 1) & t || j & (t >> 1))) //判断是否合法
{
int w = lowbit(j); //第i行状态中1的个数
for(int tt = w; tt <= k; tt ++) //枚举棋子数量
f[i][j][tt] += f[i - 1][t][tt - w];
}
cout << f[n][0][k]; //输出
return 0;
}