[编程题]八皇后
- 热度指数：9648 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。 给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。
输入描述:
每组测试数据占1行，包括一个正整数b(1 <= b <= 92)
输出描述:
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。
示例1
输入
1 92
输出
15863724 84136275
没人吐个槽吗，输入示例是2，1，92；2应该是case个数，输出的只有第一和第92个八皇后串共两个case，而实际输入是没有case个数的，直接输入i，输出第i个八皇后串。题是水题，唯一坑点
#include<bits/stdc++.h>
using namespace std;
int cb[9][9];
set<string> s;
string str;
int judge(int x,int y){
for(int i=1;i<=8;i++)if(cb[i][y]==1)return 0;
for(int i=1;i<=8;i++)if(cb[x][i]==1)return 0;
for(int i=1;i<min(x,y);i++)if(cb[x-i][y-i]==1)return 0;
for(int i=1;i<x&&y+i<9;i++)if(cb[x-i][y+i]==1)return 0;
return 1;
}
void init(int x){
if(str.size()==8){
s.insert(str);
return;
}
if(x>8)return;
for(int i=1;i<9;i++){
int tmp=judge(x,i);
if(tmp==1){
cb[x][i]=1;
char ch=i+'0';
str+=ch;
init(x+1);
cb[x][i]=0;str.pop_back();
}
}
}
int main(){
init(1);
int index;
while(cin>>index){
int cnt=1;
for(auto iter=s.begin();iter!=s.end();iter++,cnt++)if(cnt==index){cout<<*iter<<endl;break;}
}
return 0;
}
编辑于 2020-03-14 12:46:42
回复(7)
看了大家写的，基本思路就是DFS。DFS一般用递归实现，而我更喜欢用栈来实现。
所以我的算法是基于栈的DFS:
#include<iostream>
(720)#include<cstdio>
#include<cstring>
(803)#include<vector>
#include<stack>
(850)#include<string>
using namespace std;
vector<string> Queue;
int visit[9][9];//遍历矩阵，只有为0才表示可以访问
struct Statue{
int row;
int col;
Statue(int r,int c): row(r),col(c) {}
};
string loadChoice(stack<Statue> myStack){
if(myStack.empty()){
string str = "";
return str;
}
Statue temp = myStack.top();
myStack.pop();
return loadChoice(myStack)+to_string(temp.col);
}
//void display(stack<Statue> myStack){
// if(!myStack.empty()){
// Statue temp = myStack.top();
// myStack.pop();
// display(myStack);
// printf("%d %d\n",temp.row,temp.col);
// }
//}
void add(Statue a){
int row = a.row;
int col = a.col;
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
if(i==row || j==col || i-row==j-col || i+j==row+col){
visit[i][j]++;
}
}
}
}
void sub(Statue a){
int row = a.row;
int col = a.col;
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
if(i==row || j==col || i-row==j-col || i+j==row+col){
visit[i][j]--;
}
}
}
}
void DFS(){//以行为行经路线
memset(visit,0,sizeof(visit));
stack<Statue> myStack;
stack<int> myFlag;
myStack.push(Statue(0,0));//这不是一个有效点,有效点为(1,1)-(8,8)
myFlag.push(1);//从1开始遍历每一列
while(!myStack.empty()){
Statue temp = myStack.top();
for(;myFlag.top()<=8;myFlag.top()++){
if(visit[temp.row+1][myFlag.top()]==0 ){//表示可以访问
if(temp.row+1==8){
string str = loadChoice(myStack)+to_string(myFlag.top());
Queue.push_back(str.substr(1));
continue;
}
myStack.push(Statue(temp.row+1,myFlag.top()));
add(Statue(temp.row+1,myFlag.top()));
myFlag.top()++;
myFlag.push(1);
break;
}
}
if(myFlag.top()==9){//表示这种状态已经走不下去了
sub(myStack.top());
myStack.pop();
myFlag.pop();
}
}
}
int main(){
DFS();
int number;
while(cin>>number){
cout<<Queue[number-1]<<endl;
}
return 0;
}
发表于 2020-05-12 17:42:53
回复(0)
//这是一道典型的DFS回溯题目
//注意削枝即可
#include<stdio.h>
#include<algorithm>
using namespace std;
int ans[92];//定义解空间
int a[8];//定义临时解；
bool pan[8][8]; //定义棋盘
int flag=0; //标记个数
bool panduan(int x,int i)
{
for(int j=0;j<x;j++)
for(int k=0;k<8;k++)
if(pan[j][k]&&(k==i||k==i-(x-j)||k==i+(x-j))) //判断是否可以放置
return false;
return true;
}
int translate(int a[]) //此数组转换成一个十进制数
{
int count=0;
for(int i=0;i<8;i++)
{
count*=10;
count+=a[i];
}
return count;
}
void DFS(int x)
{
if(x==8)
{
ans[flag++]=translate(a); //如果到底了 那么放入数组
return;
}
for(int i=0;i<8;i++) //如果还可以放，寻找可以放的
{
if(panduan(x,i))
{
pan[x][i]=true; //代表放子
a[x]=i+1;
DFS(x+1);
pan[x][i]=false;
}
}
}
int main()
{
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
pan[i][j]=false; //初试化棋盘
DFS(0); //从零开始递归
sort(ans,ans+92); //排序，因为要输出
int n;
while(~scanf("%d",&n))
{
printf("%d\n",ans[n-1]); //注意题目给的n在数组中是n-1
}
}
发表于 2018-03-21 11:26:52
回复(0)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int visit1[100],visit2[100],visit3[100];
int number[9];
vector<int> allAnswer;
void dfs(int row)
{
if(row == 9)
{
int answer=0;//忘记初始化为0了
for(int i=1; i<=8; i++)
{
answer += number[i] * pow(10,8-i);
}
allAnswer.push_back(answer);
return;
}
for(int i=1; i<=8; i++)
{
if(!visit1[i] && !visit2[row+i] && !visit3[row-i+8])
{
visit1[i] = 1;
visit2[row+i] = 1;
visit3[row-i+8] = 1;
number[row] = i;
dfs(row+1);
visit1[i] = 0;
visit2[row+i] = 0;
visit3[row-i+8] = 0;
}
}
return;
}
int main()
{
dfs(1);
sort(allAnswer.begin(),allAnswer.end());
int n;
while(scanf("%d",&n) != EOF)
{
printf("%d\n",allAnswer[n-1]);//忘记n-1了
}
return 0;
} 样例第二个输出是错的，太坑了。。。
发表于 2021-05-02 15:08:58
回复(0)
#include <stdio.h>
int DFS(int row, int col[], int ans[][8], int len){
for(int i=0; i<8; i++){ // 遍历当前行的每一列
int flag = 1; // 标记当前列是否满足条件
for(int j=0; j<row; j++){ // 遍历前面行的确定的列号
int dis = row-j; // 前面行与当前行的距离
if((col[j]+dis)==i || (col[j]-dis)==i || col[j]==i){ // 是否在同一列或同一斜线上
flag=0;
break;
}
}
if(flag){
col[row] = i;
ans[len][row] = i+1;
if(row+1==8){
for(int j=0; j<8; j++)
ans[len+1][j] = ans[len][j];
len++;
}
else
len = DFS(row+1, col, ans, len);
}
}
return len;
}
int main(){
int n;
int col[8]; // 已确定列号
int ans[93][8]; // 满足条件的序列
int len = 0; // 序列个数
len = DFS(0, col, ans, len);
while(scanf("%d", &n)!=EOF){
for(int j=0; j<8; j++)
printf("%d", ans[n-1][j]);
printf("\n");
}
return 0;
}
发表于 2021-03-15 11:48:49
回复(0)
参考了算法笔记的剪枝技巧
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<stdlib.h>
using namespace std;
int p[9];//用来存放每一行的列数，从1开始
vector<int> vi;
bool hashtable[9];//用来标记列是否放入
void generatep(int row){//从第index行开始填入
if(row == 9){//表示找到一个结果，将其转化为整数存入vi
int sum = 0;
for(int i = 1; i <= 8; i++){
sum += p[i] * pow(10, 8 - i);
}
vi.push_back(sum);
return;
}
for(int x = 1; x <= 8; x++){//遍历第x列
if(hashtable[x] == false){
bool flag = true;
/*for循环用来剪枝*/
for(int pre = 1; pre < row; pre++){//遍历之前填入的结点
//x为index的列，p[pre]为pre的列
if(abs(row - pre) == abs(x - p[pre])){//对角线上的结点相同
flag = false;
break;
}
}
if(flag){//可以填入，直接向下填入，递归访问
p[row] = x;
hashtable[x] = true;
generatep(row+1);
hashtable[x] = false;//回溯还原
}
}
}
}
int main(){
int b;//根本就没有case个数的输入
while(cin >> b){
generatep(1);
sort(vi.begin(), vi.end());
cout << vi[b - 1]<< endl;
}
return 0;
}
发表于 2021-01-26 12:37:48
回复(0)
/*
*
*打表所有的皇后列序列，然后输出，关键是打表序列的存储方式。
*/
#include<bits/stdc++.h>
using namespace std;
const int NUM = 8;
const int maxn = 1e2;
vector<string> v; //存储每次的皇后序列 因为搜索的过程就是字典序的 所以生成的序列也是字典序的
string a;
bool vis[3][20]; //一位分别表示 同一列 同一个主对角线 同一个副对角线 是否有皇后了
int n;
void DFS_CUT(int cur) //剪枝搜索 打表
{
if(cur == NUM)
{
v.push_back(a); return ;
}
else for(int i = 0;i < NUM; i++)
{
if(!vis[0][i] && !vis[1][i+cur] && !vis[2][i-cur+NUM]) //剪枝判断
{
a[cur] = i+1+'0';
vis[0][i] = vis[1][i+cur] = vis[2][i-cur+NUM] = true;
DFS_CUT(cur+1);
vis[0][i] = vis[1][i+cur] = vis[2][i-cur+NUM] = false; //回溯
}
}
}
int main()
{
ios::sync_with_stdio(false);
memset(vis, false, sizeof(vis));
a = string(NUM, ' '); //拿string做数组用存每次的皇后列序列 所以必须事先开辟空间
DFS_CUT(0); //貌似vector里不能放数组 所以放的string
while(cin >> n)
{
cout << v[n-1] << "\n";
}
return 0;
}
发表于 2021-01-22 11:15:03
回复(0)
【N皇后关键点：放置位置条件判断+DFS】
1.放置位置条件判断
行号-列号之差相等: 在同一条正对角线 ( 左上角到右下角的斜线 )
行号+列号之和相等: 在同一条次对角线 ( 右上角到左下角的斜线上 )
2.DFS（i）
i为放置的行号，遍历时从i = 1开始（第一行开始放）
以 i = n+1为结束条件，表示放置完毕，该方法可行
#include<iostream>
(720)#include<vector>
#include<math.h>
using namespace std;
int pos[9]; //i代表当前串的行号，pos[i]代表当前串的列号
vector<int> v; //存放最终用来比较的b的皇后串
void dfs(int cur)
{
if(cur == 9)
{
int sum = 0;
for(int i=1;i<=8;i++) //将当前的位置串转换为十进制 ：即对应于b的皇后串
{
sum += pos[i]*pow(10,8-i);
}
v.push_back(sum);
}
else
{
for(int i=1;i<=8;i++)
{
bool flag = true; //标记当前放置位置是否不满足条件
pos[cur] = i;
for(int j=1;j<cur;j++)
{
if(pos[cur]==pos[j]||cur-pos[cur]==j-pos[j]||cur+pos[cur]==j+pos[j]) //关键点！！
{
flag = false;
break;
}
}
if(flag) dfs(cur+1);
}
}
}
int main()
{
dfs(1); //从第一行开始放，递归遍历
int n;
while(cin>>n)
{
cout<<v[n-1]<<endl;
}
return 0;
}
发表于 2020-04-16 10:52:20
回复(0)
#include<bits/stdc++.h>
using namespace std;
vector<int> vt;
int p[9];
bool h[9]= {false};
void solve(int index) {
if(index==9) {
int temp=0;
for(int i=1; i<=8; i++)
temp=temp*10+p[i];
vt.push_back(temp);
return;
}
for(int x=1; x<=8; x++) {
if(h[x]==false) {
bool tag=true;
for(int pre=1; pre<index; pre++) {
if(abs(index-pre)==abs(x-p[pre])) {
tag=false;
break;
}
}
if(tag==true) {
p[index]=x;
h[x]=true;
solve(index+1);
h[x]=false;
}
}
}
}
int main() {
int n,t;
solve(1);
while(cin>>n) {
cout<<vt[n-1]<<endl;
}
}
发表于 2020-03-23 11:46:27
回复(0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> vec;
int q_rank[8]; //第行的皇后所在的列
bool is_valide(const int& row,const int& rank){ //row行 rank列是否合法
if(row==0)
return true;
for(int i=0;i<row;i++){
if(rank == q_rank[i])
return false;
if(row + rank ==i + q_rank[i])
return false;
if(row - rank == i- q_rank[i])
return false;
}
return true;
}
string to_string(){ //把q_rank转换为string
string str;
for(auto a:q_rank)
str += to_string(a+1);
return str;
}
void dfs(int row,int rank){
if(is_valide(row,rank))
{
q_rank[row] = rank;
if(row == 7){
vec.push_back(to_string());
return;
}else
for(int i=0;i<8;i++)
dfs(row+1,i);
}
return ;
}
inline void eight_queen(){ //八皇后问题入口
for(int i=0;i<8;i++) //0行的0到7列依此开始深度优先遍历
dfs(0,i);
}
int main(){
eight_queen();
int n=6;
while(cin>>n && n<=92){
cout<<vec[n-1]<<endl;
}
return 0;
} 深度优先搜素遍历
编辑于 2020-02-29 11:49:20
回复(0)
参考《算法竞赛入门》第一版
#include <stdio.h>
int rst[92][8];
int idx=0;
int C[8];
void search(int cur)
{//递归回溯
if(cur == 8)
{
for(int i=0;i<8;i++)
{
rst[idx][i]=C[i];
}
idx++;
}
else
{
for(int i=1;i<=8;i++)
{
int ok=1;
C[cur]=i;
for(int j=0;j<cur;j++)
{
if(C[cur] == C[j] ||C[cur]+cur == C[j]+j || C[cur] - cur == C[j] - j)
{
ok =0;
break;
}
}
if(ok)
search(cur+1);
}
}
}
int main()
{
int b;
search(0);
while(scanf("%d",&b)!=EOF)
{
for(int i=0;i<8;i++)
printf("%d",rst[b-1][i]);
printf("\n");
}
return 0;
}
发表于 2019-08-02 23:01:34
回复(0)
#include <stdio.h>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
int board[8][8];//棋盘
int pos[9]; //存储每一行放置的棋子位置
long temp=0;
vector<int> res; //存放最终的92组解
bool check(int xi,int xj){ //遍历棋盘上已经放的子 判断是否与（i,j）同列 同对角线
for(int i=0;i<xi;i++){
for(int j=0;j<8;j++){
if((board[i][j]==1)&&(j==xj||abs(i-xi)==abs(j-xj)))
return false;
}
}
return true;
}
void DFS(int row){
if(row==8){
temp=0;
for(int i=1;i<=8;i++) //将pos[1]...pos[8]拼接到一起
temp+=pos[i]*pow(10,8-i);
res.push_back(temp);
return;
}
for(int col=0;col<8;col++){
if(check(row,col))
{
pos[row+1]=col+1; //第1行 第2行 第3行 ..第8行 序号从1开始
board[row][col]=1;
DFS(row+1);
board[row][col]=0;
}
}
}
int main(){
int n;
for(int i=0;i<8;i++)
for(int j=0;j<8;j++){
board[i][j]=0;
}
DFS(0); //row从0开始，执行DFS(7)后得到一个结果，然后row=8
sort(res.begin(),res.end());
while(scanf("%d",&n)!=EOF)
printf("%d\n",res[n-1]);
}
编辑于 2019-03-22 22:47:52
回复(0)
递归求出符合要求的串，思路比较清晰
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
bool isOK(string queen) //判断一个串各皇后位置是否冲突
{
for (int i = 0; i < queen.size(); i++)
{
for (int j = i + 1; j < queen.size(); j++)
{
if (j - i == (queen[j] - '0') - (queen[i] - '0') || j - i == (queen[i] - '0') - (queen[j] - '0'))
return false;
}
}
return true;
}
void getQueen(string queen, int begin, vector<string>& queen_list) //求一个串排除皇后位置冲突后的全排列
{
if (begin == queen.size() - 1 && isOK(queen)) queen_list.push_back(queen);
for (int i = begin; i < queen.size(); i++)
{
if (i != begin && queen[i] == queen[begin]) continue;
swap(queen[begin], queen[i]);
getQueen(queen, begin + 1, queen_list);
swap(queen[begin], queen[i]);
}
}
int main()
{
vector<string> res;
string queen = "12345678";
getQueen(queen, 0, res);
sort(res.begin(), res.end());
int b;
while (cin >> b)
{
int sum = 0, len = res[b - 1].size() - 1;
for (int i = 0; i <= len; i++)
sum += (res[b - 1][len - i] - '0') * pow(10, i);
cout << sum << endl;
}
system("pause");
return 0;
}
发表于 2019-03-17 13:04:50
回复(0)
思路比较简单，先找出规则，同一行同一列，同一斜排不能同时有两个。
这里用递归+全局，
从第一行开始，每一行从第一个位置开始检查该位置是否能放皇后（和前面的行比较）
如果能，则寻找下一行能放的位置.....
一直走到找到全部的八个皇后位置，然后加入到全局变量。
def findAllResult(row):
global results
global tempPos
if row == 9:
tmp = ""
for i in range(1,9):
tmp += str(tempPos[i])
results.append(tmp)
else:
for i in range(1,9): #这个循环是寻找放在当前行row的合适皇后位置
tempPos[row] = i
flag = True
for j in range(1,row): #检查是否不在同一列或者斜线上
if tempPos[row] == tempPos[j] or row - j == abs(tempPos[row] - tempPos[j]):
flag = False
break
if flag: #如果放在该行位置不影响前面行的皇后则寻找下一行
findAllResult(row+1) #走到最后又会回来这里继续for循环
while True:
try:
num = int(input())
results = [] #保存着全部92种结果
tempPos = list(range(9)) #临时存放着每一行皇后的位置
findAllResult(1)
results.sort()
print(results[num-1])
except Exception:
break
编辑于 2018-09-28 20:26:43
回复(0)
Object C
#include<stdio.h>
#include<string.h>
int cnt, num, flag;
int ans[9], vis[9];
int abs(int x){
return x > 0 ? x : -x;
}
int check(int cur){
int i, j;
for(i = 1; i<cur; i++){
for(j = i+1; j<cur; j++)
if(abs(ans[i]-ans[j]) == abs(i-j)) return 0;
}
return 1;
}
void dfs(int cur){
int i;
if(flag == 1) return ;
if(!check(cur)) return ;
if(cur == 9){
num++;
if(num == cnt){
for(i = 1; i<9; i++)
printf("%d", ans[i]);
printf("\n");
flag = 1;
}
}
for(i = 1; i<9; i++)
if(!vis[i]){
vis[i] = 1;
ans[cur] = i;
dfs(cur+1);
vis[i] = 0;
}
}
int main(){
while(~scanf("%d", &cnt)){
num = 0, flag = 0;
memset(vis, 0, sizeof vis);
dfs(1);
}
return 0;
}
发表于 2018-07-24 16:53:48
回复(0)
#include<cstdio>
#include<cstring>
#include<algorithm> //利用algorithm下的next_permutation产生全排列
bool checkQueen(int *qList) { //验证一个排列是不是正确解
int i, j;
for (i=0; i<7; ++i) //因数组中各个皇后行列数已不同，故只需看在不在斜线上
for (j=i+1; j<8; ++j) //遍历下面各行的皇后，看是否符合
if (j-i == abs(qList[j] - qList[i])) //在斜线上
return false; //两个皇后在斜线上可以互相攻击，不符合
return true;
}
int main() {
int b, qList[] = {1, 2, 3, 4, 5, 6, 7, 8}, all_qList[92][8], i=0;
while (i < 92) { //空间换时间，先把92个解全找出来
if (checkQueen(qList))
memcpy(all_qList[i++], qList, 8*sizeof(int));
std::next_permutation(qList, qList+8); //变为全排列中的下一个
}
while (scanf("%d", &b) != EOF)
for (i=0; i<8; ++i)
printf("%d%s", all_qList[b-1][i], i==7 ? "\n" : "");
return 0;
}
编辑于 2018-02-16 15:02:48
回复(1)
//八皇后
#include<stdio.h>
#define MAXN 8
int cnt =0;
int num_arr[92][8];
int chess_board[8][8];
void display(){
for(int row=0;row<MAXN;row++){
for(int col=0;col<MAXN;++col){
if(chess_board[row][col])num_arr[cnt][row]=col+1;
}
}
}
void show(int num){
for(int i =0;i<MAXN;i++){
printf("%d",num_arr[num][i]);
}
printf("\n");
}
int avail_place(int row,int col)
{
int k;
for(k=0;k<MAXN;k++){
if((chess_board[row][k] && k!=col)||(chess_board[k][col] && k!=row))return 0;
}
for(k=0;row-k>=0 && col-k>=0;k++)if(chess_board[row-k][col-k])return 0;
for(k=0;row-k>=0 && col+k<MAXN;k++)if(chess_board[row-k][col+k])return 0;
for(k=0;row+k<MAXN && col-k>=0;k++)if(chess_board[row+k][col-k])return 0;
for(k=0;row+k<MAXN && col+k<MAXN;k++)if(chess_board[row+k][col+k])return 0;
return 1;
}
void put(int row){
if(row == MAXN -1){
for(int col=0;col<MAXN;col++){
if(avail_place(MAXN-1,col)){
chess_board[MAXN-1][col] = 1;
display();
cnt++;
chess_board[MAXN-1][col] = 0;
return ;
}
}
return ;
}
else{
for(int col = 0;col<MAXN;col++){
if(avail_place(row,col)){
chess_board[row][col] = 1;
put(row+1);
chess_board[row][col] = 0;
}
}
}
}
int main(){
put(0);
int num;
int idx;
while(scanf("%d",&num)!=EOF){
for(int i=0;i<num;i++){
scanf("%d",&idx);
show(idx-1);
}
}
return 0;
}
回溯法
编辑于 2017-02-03 22:26:38
回复(0)
#include <stdio.h>
#include <string.h>
int board[9]={0,0,0,0,0,0,0,0,0},count=0,boards[93][9];
int judge(int row,int col){
char vist[9]={0,0,0,0,0,0,0,0,0};
for(int i=1;i<row;vist[board[i++]]=1);
if(vist[col]) return 0;
for(int i=1;i<row;++i)
if (col+i-row==board[i]) return 0;
else if (col+row-i==board[i]) return 0;
return 1;
}
void NQueen(int N,int row){
if (row==N) memcpy(boards[++count],board,9*sizeof(int));
else{
for(int col=1;col<N;++col){
if (judge(row,col)) {
board[row]=col;
NQueen(N,row+1);
board[row]=0;
}
}
}
}
int main(){
NQueen(9,1);
for(int n;~scanf("%d",&n);)
for(int q;n-- && ~scanf("%d",&q);printf("\n"))
for(int i=1;i<9;printf("%d",boards[q][i++]));
return 0;
}
发表于 2016-09-12 15:43:28
回复(0)
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 101;
string str[maxn]; // 时间换空间
int bite[maxn] = {0}; // 记录 i th 行皇后 在 j th 列
int count = 0; // 用于计数
void solve(int num)
{
if(num == 8)
{
char tmp;
for(int i = 0; i < 8; ++i)
{
tmp = '1'+bite[i];
str[count] += tmp;
}
++count;
}
else
{
for(int i = 0; i < 8; ++i)
{
int flag = 1;
// 判断这个位置是不是能放
for(int j = 0; j < num; ++j)
{
if(i == bite[j] || (num+i == j+bite[j]) || (num-i == j-bite[j]))
{
flag = 0;
break;
}
}
// 如果能放继续放后序的皇后
if(flag == 1)
{
bite[num] = i;
solve(num+1);
}
}
}
}
int main()
{
solve(0);
int n;
int i;
cin >> n;
while(n--)
{
cin >> i;
cout << str[i-1] << endl;
}
return 0;
}
发表于 2016-08-13 10:28:34
回复(0)
/*非常朴素的八皇后问题，问题规模也已经框定好了，只要把每次得到的列号转化成要比较的十进制数字即可*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
vector<int> solut; //用来放最终的结果
int position[9]; //行号从1开始，其中下标代表行号，其中存放的内容代表列号
void DFS(int row);
int main()
{
DFS(1); //直接从第一行开始放
sort(solut.begin(), solut.end()); //这里应该不用sort因为得到的solution应该都是从小到大
int n;
while (scanf("%d", &n) != EOF)
{
printf("%d\n", solut[n - 1]); //因为vector是从0开始的
}
return 0;
}
void DFS(int row) //row代表要放入的行号,逐行放入，因为要用的是列号，而且按照习惯都是一列一列计算的
{
if (row == 9) //row==9意味着从1~8行全都放入,已完成解
{
int temp = 0;
for (int i = 1; i <= 8; i++)
{
temp += position[i] * pow(10, 8 - i); //非常朴素的计算方法_(:з」∠)_
}
solut.push_back(temp); //把得到的solution放进vector
}
else
{
for (int i = 1; i <= 8; i++)
{
position[row] = i; //i在这里代表列号
bool flag = true; //用一个标志位来标记，是否冲突
for (int j = 1; j < row; j++)
{
if (position[row] == position[j] || row - position[row] == j - position[j] || row + position[row] == j + position[j])
{
flag = false;
break;
} //这里的判断条件j - position[j]会把同一主对角线标记为同一个数字，与row - position[row]同时计算就能判断是否冲突
}//for
if (flag)
DFS(row + 1);
}
}//endif
}//DFS
发表于 2018-02-06 20:06:25
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
