世界上最好的题解😄

#include<iostream>
using namespace std;
int n,ans;
int a[20];
bool fc[20],fz[120],ff[120];
bool isok(int c,int z,int f){
	if(!fc[c]&&!fz[z]&&!ff[f])return true;
	else return false;
}
void view(){
	for(int i=1;i<=n;++i)cout<<a[i]<<" ";
	cout<<endl;
}
void dfs(int k){
	if(k==n+1){ans++;if(ans<=3)view();return;}
	for(int i=1;i<=n;++i){
		if(isok(i,k-i+100,k+i)){
			a[k]=i;
			fc[i]=true;fz[k-i+100]=true;ff[k+i]=true;
			dfs(k+1);
			a[k]=0;
			fc[i]=false;fz[k-i+100]=false;ff[k+i]=false;
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<ans;
	return 0;
}

看完别忘了点赞呦👀️

纯 dfs

如果暴力判断是否合法，那么想想都超时

所以我们可以开一个数组，记录是否合法。

$AC \ Code$

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[20];
bool used1[20],used2[20],used3[20];
void Print(){
  for (int i = 1; i <= n; i++){
    cout << a[i] << ' ';
  }
  cout << '\n';
}
void dfs(int x){
  if (x == 1 + n){
    ans++;
    if (ans <= 3){
      Print();
    }
    return;
  }
  for (int i = 1; i <= n; i++){
    if (!used1[i] && !used2[x - i + n] && !used3[x + i]){
      used1[i] = used2[x - i + n] = used3[x + i] = 1;
      a[x] = i;
      dfs(x + 1);
      used1[i] = used2[x - i + n] = used3[x + i] = 0;
    }
  }
}
int main(){
  cin >> n;
  dfs(1);
  cout << ans;
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
int amountOfQueens, queenPos[105], amountsOfMethods, outputed;  //皇后数量，皇后的位置，摆法，记录输出次数
bool column[105], conflictSlash[310], conflictBackSlash[310];   //列，正反对角线的占用情况
void dfs(int line) {
    for(int j=1; j<=amountOfQueens; ++j) {                      //对列枚举，判断能否放在这一列，由于 line-j 可能为负 +100
        if(!column[j] && !conflictSlash[line+j+100] && !conflictBackSlash[line-j+100]) {
            queenPos[line]=j;                                   //把第 line 行的皇后放在这一列
            column[j]=true;
            conflictSlash[line+j+100]=true;                     //标记对角线占用
            conflictBackSlash[line-j+100]=true;
            if(line<amountOfQueens) {                           //摆放下一个皇后
                dfs(line+1);
            } else {                                            //已经完成摆放，输出
                ++amountsOfMethods;
                if(outputed == 3) goto jump;
                for(int i=1; i<=amountOfQueens; ++i) {
                    for(int k=1; k<=amountOfQueens; ++k) {
                        if(k==queenPos[i]) cout << k << ' ';
                    }
                }
                cout << endl;
                ++outputed;
            }
            jump:                                               //恢复到之前的状态
            column[j]=false;                                
            conflictSlash[line+j+100]=false;
            conflictBackSlash[line-j+100]=false;
        }
    }
}
int main() {
    cin >> amountOfQueens;
    dfs(1);                                                     //从第一行开始放皇后
    cout << amountsOfMethods;
    return 0;
}