八皇后问题_牛客博客

前言

正文

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将 8 个皇后放在棋盘上（有8×8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即 a=b1b2…b8, 其中bi（1≤bi≤8）为相应摆法中第 i 行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数n，要求输出第n个串。串的比较是这样的:皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入描述:

输入包含多组数据。
每组数据包含一个正整数n（1≤n≤92）。

输出描述:

对应每一组输入，输出第n个皇后串。

示例1
输入

1
92

输出

15863724
84136275

参考题解

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
vector<string> res;//结果数组 
int col[10];//下标为行号，值为列号 
vector<string> v;
void dfs(int row){
	if(row==9){//row==9说明已经放完了8行的皇后，即完成了一次有效的摆放 
		string temp="";
		char ch;
		for(int i=1;i<=8;i++){//转字符串 
			ch=col[i]+'0';
			temp=temp+ch; 
		} 
		res.push_back(temp);//加入到vector中 
	}else{
		for(int j=1;j<=8;j++){//在第row行中遍历每一列
			col[row]=j;
			bool flag=true;//满足放皇后的条件 
			for(int i=1;i<row;i++){
				if(col[row]==col[i]||abs(row-i)==abs(col[row]-col[i])){//列号相同或者同一对角线 
					flag=false;//与前面某个已经摆好的皇后产生冲突 
					break;
				}	
			}
			if(flag)dfs(row+1); //该位置与之前所有位置都不冲突，则进入下一行
		}
	}
}

int main(){
	int n;
	while(cin>>n){
		dfs(1);
		sort(v.begin(),v.end());//从小到大字典序排序（后来发现不用排序其实，因为循环下来，本来就是vector里的本来就是从小到大的）
		//v.clear();
		cout<<res[n-1]<<endl;		
	} 
	return 0;
}