题目描述
在 n×n 的棋盘上放 k 个国王,国王可攻击相邻的 8 个格子,求使它们无法互相攻击的方案总数。
输入格式
共一行,包含两个整数 n 和 k。
输出格式
共一行,表示方案总数,若不能够放置则输出0。
数据范围
1≤n≤10,
0≤k≤n^2
样例
输入样例:
3 2
输出样例:
16
算法1
(状态压缩DP)
时间复杂度
$O()$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N=12,M=1<<10,K=110;
vector<int>state;
vector<int>head[M];
int cnt[M];
LL f[N][K][M];
int n,m;
bool check(int a)
{
for(int i=0;i<n;i++)
{
if((a>>i&1)&&(a>>(i+1)&1))
{
return false;
}
}
return true;
}
int count(int a)
{
int res=0;
for(int i=0;i<n;i++)
{
res=res+(a>>i&1);
}
return res;
}
int main()
{
cin>>n>>m;
for(int i=0;i<1<<n;i++)
{
if(check(i))
{
state.push_back(i);
cnt[i]=count(i);
}
}
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)==0&&check(a|b))
{
head[i].push_back(j);
}
}
}
f[0][0][0]=1;
for(int i=1;i<=n+1;i++)
{
for(int j=0;j<=m;j++)
{
for(int a=0;a<state.size();a++)
{
for(auto b:head[a])
{
int c=cnt[state[a]];
if(j>=c)
{
f[i][j][state[a]]+=f[i-1][j-c][state[b]];
}
}
}
}
}
cout<<f[n+1][m][0]<<endl;
return 0;
}