当前位置:首页 > 搜索 > 深度优先搜索 > 正文
NOI2.5-1756八皇后
263+

题目大意:8皇后问题共有92种摆法,按照字典需,第m种方案的摆放是什么呢?

题目描述

会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法,定义一个皇后串a与之对应,即a=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

解题思路

搜索预处理,将8皇后的92中摆放方案存到一个数组中,为了避免用二维数组、嵌套循环保存输出、浪费空间,可以用一个整型遍历把方案存起来,因为方案只是一个8位数而已。

搜索时,记录第k行填了什么(x[k]),列是否填过(y[i]),左斜是否填过(l[i+k]),右斜是否填过(r[i-k+8]),+8是防止负数下标越界。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,

NOI2.5-1756八皇后:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter