奥赛一本通 1214

发布于 2020-05-29  13 次阅读


T1214:八皇后

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 × 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。

对于某个满足要求的8皇后的摆放方法,定义一个皇后串a与之对应,即a=b1b2…b8a=b1b2…b8,其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解(即92个不同的皇后串)。

给出一个数b,要求输出第b个串。串的比较是这样的:皇后串x置于皇后串y之前,当且仅当将x视为整数时比y小。

【输入】

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数b(1≤b≤92)。

【输出】

输出有n行,每行输出对应一个输入。输出应是一个正整数,是对应于b的皇后串。

【输入样例】

2
1
92

【输出样例】

15863724
84136275

问题描述

1.测试结果:测试点1-9WA,测试点10AC,总分10

2.我的思路:打表,八皇后的解打出后排序(因为是用原本的错程序打表以防万一)O(1)输出即可(100分)

3.错程序:

#include<bits/stdc++.h>
using namespace std;
bool b[9],c[16],d[16];
int a[100];
int s=0,n,x[93];
int print ()
{
	s++;
	for(int j=1;j<=n;j++)
		if(x[j]==s) 
		{
			for(int i=1;i<=8;i++)
				cout<<a[i];
			cout<<endl;
		}	
}
int dfs(int i)
{
	for(int j=1;j<=8;j++)
		if((!b[j])&&(!c[i+j])&&(!d[i-j+7]))
		{
			a[i]=j;
			b[j]=1;
			c[i+j]=1;
			d[i-j+7]=1;
			if(i==8) print();
			else dfs(i+1);
			a[i]=0;
			b[j]=0;
			c[i+j]=0;
			d[i-j+7]=0;
		}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>x[i];
	dfs(1);
	return 0;
}

4.错误分析:(虽然不是我自己的错误但还是超级无语果然菜到一定境界了)对每次的八皇后解判断是否在询问的数字中,是则输出。最后的输出顺序是八皇后解的顺序,而非问询顺序,应该将所有解存储(或者打表)下来后询问一次做一次

5.标准程序:打表应该所有人都会写吧(P.S:错程序的DFS是对的)


花开花败总归尘。 阴阳化生,清浊自分。