- #include<bits/stdc++.h>
- using namespace std;
- int n,ans=0;
- bool flag=true; // 标记这一组全排列是否可行
- int num[1010]={0}; //num[i] 表示第 i 行皇后所在第几列
- int vis[1010]={0}; // 判断数字是否用过
- void dfs(int y){ // 参数 y 表示第 y 层
- // 搜完一组全排列方案
- flag=true; // 初始化为 true
- if(y==n+1){
- //num[i] 两两比较, 只需判断不同皇后是否在同一对角线即可,
- // 全排列已经保证了不同行不同列
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++){
- if(abs(num[i]-num[j])==abs(i-j) && i!=j){
- flag=false;
- }
- }
- }
- if(flag){
- ans++;
- }
- return;
- }
- // 全排列递归部分
- for(int i=1;i<=n;i++){
- // 判断数字是否使用过
- if(!vis[i]){
- vis[i]=true; // 标记这一层深搜时数字 i 已使用
- num[y]=i; // 第 y 层使用数字 i
- dfs(y+1); // 进行下一层搜索
- vis[i]=false; // 递归返回时清楚本层标记, 将数字 i 置为未使用
- }
- }
- }
- int main()
- {
- cin>>n;
- dfs(1);
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3415554.html