dp + dfs (有注释)
dp
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;
int n, k;
vector<int> state;
int cnt[M];
vector<int> head[M];
LL f[N][K][M]; //f[i][j][state] 已经摆放完前i行 摆了j个国王 且第i行是state
//划分: 最后一步固定是state (a) 那么上一步来划分是啥 是 state(b)
// 每种划分加起来:已经摆放i - 1行,摆了j - cnt[a] i行是state(b) f[i - 1][j- c][b];
bool check(int state){ // 没有相邻的两个1
for(int i = 0; i < n - 1; i++)
if(state >> i & 1 && state >> i + 1 & 1) return false;
return true;
}
int count(int x){// 计算1的数量
int res = 0;
while(x) res++, x -= x & -x;
return res;
}
int main(){
cin >> n >> k;
// 先预处理一下每行可能的状态(同行无相邻) 最多2 ^ n种状态
for(int i = 0; i < 1 << n; i++){
if(check(i)) state.push_back(i);
cnt[i] = count(i);
}
// 预处理一下每个状态之间能转换的状态
// 两行之间没有相同列有1 ------ !(i & j)
// 两行合并之后没有相邻1 ------ check(i | j)
for(auto i: state)
for(auto j: state)
if(!(i & j) && check(i | j)) head[i].push_back(j);
f[0][0][0] = 1;
for(int i = 1; i <= n + 1; i++)
for(auto a: state)
for(auto b: head[a])
for(int t = cnt[a]; t <= k; t++)
f[i][t][a] += f[i - 1][t - cnt[a]][b];
cout << f[n + 1][k][0] << endl;
return 0;
}
dfs (TLE)
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 12;
int n, k;
LL res;
int cnt[N][N]; // 表示冲突个数
void put(int x, int y){
//以(x, y)为中心的9个位置 冲突加1
for(int a = x - 1; a <= x + 1; a++)
for(int b = y - 1; b <= y + 1; b++){
if(a < 0 || a >= n || b < 0 || b >= n) continue;
cnt[a][b]++;
}
}
void take(int x, int y){
//以(x, y)为中心的9个位置 冲突减1
for(int a = x - 1; a <= x + 1; a++)
for(int b = y - 1; b <= y + 1; b++){
if(a < 0 || a >= n || b < 0 || b >= n) continue;
cnt[a][b]--;
}
}
void dfs(int a, int b, int t){
if(t == k){
res++;
return;
}
if(b == n) a++, b = 0;
if(a == n) return;
// 放
if(!cnt[a][b]){
put(a, b);
dfs(a, b + 1, t + 1);
take(a, b);
}
// 不放
dfs(a, b + 1, t);
}
int main(){
cin >> n >> k;
// 从(0, 0)开始放国王 并且已经放0个
dfs(0, 0, 0);
cout << res << endl;
return 0;
}