dfs又称为深度优先搜索算法

我们采用先了解dfs的基本思路

然后根据n皇后一题

进行dfs算法讲解

大家如果是来看n皇后问题的实现

可以直接看到后面的代码

————————————我是分割线

首先博主先大概讲解一下dfs的思路

dfs涉及到了递归与回溯

博主在下面会详细的介绍

先看下思路：

dfs就是按照你所给的顺序

先向一条路一直走

直到走到尽头后

才回头（回溯）

然后找到回头后可以选择的下一条道路

然后再走到尽头

直到把所有道路走完

或者满足你要找到的结果然后停下

可能比较难理解

我们以n皇后问题

进行详解

#include<stdio.h>
#include<iostream>
using namespace std;
#include<math.h>
int rk[20];//存储皇后所在地，下标表示所在行，下标的数字表示所在列
bool vis[20];//只能存储true和false，用来记录该列是否被使用过
int n, cnt = 0;//cnt表示有多少种方法
bool flag;
void dfs(int pos)
{
	if (pos == n + 1)//判定条件：即已经放置完了n个皇后，也就是走到了尽头
	{
		cnt++;//能够通过的方法加一
		if (cnt <= 3) 
		{
			for (int i = 1; i <= n; i++)
			{
				cout << rk[i] << " ";
			}
			cout << endl;//满足题目输出前三项
		}
	}
	for (int i = 1; i <= n; i++)//i代表第几列，向下走
	{
		if (vis[i] == false)//如果该列没有被标记过
		{
			flag = true;
			for (int j = 1; j < pos; j++)
			{
				if (abs(rk[j] - i) == abs(j - pos))//abs是对于数值取绝对值的意思
//划重点啦：n皇后是否在一条斜线上可以用需要检测的两个皇后所在的位置行与行，列与列相减
//相同的话就代表在一条斜线上，大家可以自己试一下
				{
					flag = false;//如果在一条斜线上面就让让flag为假，与下面对应
					break;
				}
			}
			if (flag)//为真的话代表可以在该处放置n皇后
			{
				rk[pos] = i;//放置n皇后
				vis[i] = true;//标记该列已经放置n皇后
				dfs(pos + 1);//进行递归，也就是不断向前走
				vis[i] = false;//递归回来，将该处取消标记
			}
		}
	}
}
int main() {
	cin >> n;
	dfs(1);
	cout << cnt;
	return 0;
}