*八皇后是一道深度优先搜索(DFS)题目,如果对于其概念并不清楚,可以去看:
Macw07的深度优先搜索 DFS : https://www.acgo.cn/discuss/study/19056
正题开始:
题目大意:
在8*8的棋盘放8个不在同一行,同一列,同意对角线的皇后,
每行输出一个长度为8的字符串：R1R2R3R4R5R6R7R8(0 <Ri <9，表示第i行，皇后所在的位置)
解题思路:
1.首先,使用递归(深搜)进行查找,利用a数组存下列的位置,并在找齐8个皇后所在位置后输出:
2.在这样的循环里遍历位置
然后可以发现其实题目要求查找的是列,行就按1,2,3,4,5,6,7,8定就好,所以可以将行的遍历省去,将x当作行:
3.检查当在前的位置摆放皇后是否合法,既同一行,同一列,同一对角线是否有其他皇后的存在?
(同一行不用检查,因为棋子的摆放位置就是按照x一行一行枚举下来的)
这里我们使用一个二维数组,记录棋子位置的摆放
如果有一个棋子在第x行第i列摆放
将其标记
这样,我们就可以顺利的检查摆放位置是否合法了
浅提一下如何检查对角线:
首先,要知道对角线有两条,比如,我们在第一行第三列下放棋子,我们就需要检查
这两条对角线.
然后,因为我们遍历棋子位置是有序遍历的,所以如果要检查(3,3)这个点的两条对角线,只要检查(1,1),(2,2)两个位置和(1,5),(2,4)两个位置就可以了(后面的位置都没有遍历到,不需要检查)
4.如果摆放位置合法,记录下来
伪代码:
*看伪代码并填充,可以帮助CSP-J/S初赛备考生
正解代码:
