题目描述
在 n×n
的棋盘上放 k
个国王,国王可攻击相邻的 8
个格子,求使它们无法互相攻击的方案总数。
输入格式
共一行,包含两个整数 n
和 k
。
输出格式
共一行,表示方案总数,若不能够放置则输出0
。
数据范围
1≤n≤10
,
0≤k≤n2
样例
输入样例:
3 2
输出样例:
16
算法
大鹏姐姐(状压版)
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int N=12,M=1<<10,K=110;
int n,m;
vector<int> state;
int cnt[M];
vector<int> head[M];
long long f[N][K][M];
//所有只摆在前i行,
//已经摆了j个国王,
//且第i行的摆放状态是s的所有方案的集合。
bool check(int state){
//cout<<state<<" "<<(state>>0 &1)<<endl;
for(int i=0; i<n; i++)
//当i=0时,二进制数不左移,所以&1 是二进制数的个位
if((state>>i &1) && (state>>i+1 &1))
//查相邻两位是否都摆放了国王(book)
return 0;
return 1;
}
int count(int state){//数一数此行拜访了多少个国王
int res=0;
for(int i=0; i<n; i++) res+=state>>i &1;
return res;
}
int main(){
cin>>n>>m;
for(int i=0; i<1<<n; i++){//筛同行(从0到1<<n -1)
if(check(i)){
state.push_back(i);
cnt[i]=count(i);
}
}
//筛前后两行间 (vector的下标从0开始)
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(b);
}
}
f[0][0][0]=1;
for(int i=1; i<=n+1; i++){
//(到n+1是为了将第n行的所有答案汇总到f[n+1][m][0]处)
for(int j=0; j<=m; j++){
//(存在不放国王的情况)
for(int a=0; a<state.size(); a++){
//(vector)
for(int b:head[a]){
//枚举所有对于state[a]来说合法的上一行
int t=state[a],c=cnt[state[a]];
if(j>=c && j-c<=m)
f[i][j][t]+=f[i-1][j-c][b];
}
}
}
}
cout<<f[n+1][m][0]<<endl;
return 0;
}
%%%tql,不过没有 云yie~ 强
e…
hh
hh
qp