P1219|P1219 八皇后 题解 （dfs 深度优先搜索）
P1219 八皇后
- 题目
- 分析
- 题目大意
- 解题思路
- 代码
- 传送门
题目 检查一个如下的6 x 6的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
文章图片
上面的布局可以用序列2 4 6 1 3 5来描述，第i个数字表示在第i行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
【P1219|P1219 八皇后 题解 （dfs 深度优先搜索）】这只是跳棋放置的一个解。请编一个程序找出所有跳棋放置的解。并把它们以上面的序列方法输出。解按字典顺序排列。请输出前3个解。最后一行是解的总个数。
输入格式：
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
输出格式：
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输入输出样例
输入样例#1：
6
输出样例#1：
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
分析 题目大意 经典题目了，所不同的的是，本题要求依次输出前三个排法的列数，同时记录解法的个数并输出。
解题思路 这里采用的是深搜去遍历所有的可能排法。我们需要做的就是尽可能去简化在判定能否放置棋子时的步骤。
若要放置一枚棋子，需要判定该棋子同一行、同一列和左右两条对角线是否存在别的棋子，如果一个一个去遍历，不仅复杂还会花费大量的内存去存储每一个点，所以我们需要寻找方法来简化问题。
首先观察题目中所给出的图可以发现，若设棋盘的行列坐标分别为y，x，那么，与p点所在的对角线符合以下规律：
- 对于p点从右上到左下的对角线，x+y相等；
- 对于p点从左上到右下的对角线，x-y相等；
代码
//P1219
#include
using namespace std;
//整型全局变量默认初始化为0
const int Max = 14;
//数据范围在6到13之间
int n;
int ans[Max];
//存放皇后所在的列数
int sum;
//对于从右上到左下的对角线，他们的行列之和相等，同样的，对于从左上到右下的对角线，他们的行列之差相等，为避免出现负数，这里又加上了总数n
int chess[3][Max*2];
//chess[0][i]=1表示第i列已被放置皇后，chess[1][i]=1表示行列和为i的对角线已存在皇后（右上到左下），chess[2] [i]=2表示行列之差加上n的值为i的对角线已存在皇后（左上到右下） void dfs(int i){
if(i>n)
{
sum++;
if(sum>3) //题目要求只输出前三个解
return;
else{
for(int i=1;
i<=n;
i++){
if(i == 1)
cout<>n;
dfs(1);
cout<< 传送门 P1219
推荐阅读
- 八、「料理风云」
- 2018.03.18
- 被新冠“病毒”感染的日常生活（八）
- 【同心同舵】郑友贤第八季思维导图武林计划No.15《点评作业5》
- 第二十八封信
- 21天高情商活法功课|21天高情商活法功课 ，第八天
- 未来丛林历险记
- 八零后也已经老了
- 父母链接八～未了情结
- 暴君公司|暴君公司 第十八章 做会员吗