思想:
DFS
。res
为方案数,res <= 3
输出当前方案。k = i + u
或 k = i - u
,另,由于 i - u
的值可能为负数,因此考虑增加偏移量 k = i - u + n
保证下标合法。代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
bool y[N], l[N], r[N];
int n, res;
int ans[N];
void dfs(int u){
if(u == n){ // 说明放满了棋子
res ++; // 记录答案 res + 1
if(res <= 3){ // res <= 3 输出方案
for(int i = 0; i < n; i ++) cout << ans[i] << ' ';
cout << endl;
}
return ;
}
for(int i = 0; i < n; i ++){
if(!y[i] && !l[u + n + i] && !r[u + n - i]){
y[i] = l[u + n + i] = r[u + n - i] = 1; // 标记
ans[u] = i + 1; // 存入答案数组
dfs(u + 1); // 递归到下一层
y[i] = l[u + n + i] = r[u + n - i] = 0; // 恢复现场
}
}
}
void solve(){
cin >> n;
dfs(0);
cout << res << endl;
}
int main(){
solve();
return 0;
}