目录

• 🌟一、了解DFS
• • ✨1、DFS（Depth First Search）
  • ✨2、回溯——DFS核心
  • ✨3、重学递归——DFS本质
• 🌟二、AcWing 842. 排列数字
• • ✨1、题目
  • ✨2、思路
  • ✨3、AC代码
• 🌟三、AcWing 843. n-皇后问题
• • ✨1.题目
  • ✨2、思路一
  • • ①、ac代码：
    • ②、代码剖析
    • ③、row数组的理解
    • ④、dg[x + y] = udg[x - y + n]的理解
  • ✨3、思路二
• 🌟四、同类习题分享
• 🌟五、结尾：

前言
你好啊，我是一名算法小白，，算法入门确实困难，肝了半天才把DFS给肝完😖，蓝桥杯将至，来一起学学蓝桥杯常考算法吧，这是我的题解，先上几道模板题，后面还有例题分析，我相信你认真看完，认真把题做了，一定可以学会的。
同时欢迎关注我的专栏，用心写题解，不多bb，开干🚀🚀🚀

这个表情也是我做的，需要可以取走hhh

🌟一、了解DFS

✨1、DFS（Depth First Search）

DFS搜索是搜索中的一种，即深度优先搜索（Depth First Search），俗称暴搜， 其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次，简要来说就是从头走到尾，如果没找到,就一层一层地返回重新找另一个子链，然后再继续深入找，左边找完找右边。 本质确实就是： 递归 左图就是DFS的过程

✨2、回溯——DFS核心

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。下图为遍历路线，所以假设没找到，DFS就是这样子走的。从1开始， 1-2的那个回溯是指 5》4》2》1。

✨3、重学递归——DFS本质

如果你基础比较好可以直接跳过，感兴趣或者没学过可以看看，另外，我们一直都知道递归就是自己调用自己，但是看到一些递归自己都分辨不清，可以参考一下dalao的图

🌟二、AcWing 842. 排列数字

✨1、题目

题目链接传送门

✨2、思路

排列数字是DFS的经典例题，DFS搜索的形式都是树的形状，就如这道题可以转化为树 如下图

由此可以定义一个数组path[N] 来保存当前的路径/模拟DFS的过程，当这个数组数字填满的时候，就把当前的排列数字输出出来，然后回溯的时候就需要一个核心操作回溯(恢复现场)，比如走到1 2 3 回溯 到结点的过程为 123 —>12—>1 ，这个过程的核心操作就是需要把原来的位置恢复到原有状况，然后递归。

✨3、AC代码

#include using namespace std;const int N = 7;int n;int path[N]; //保存路径bool st[N]; //用于记录该店是否来过  反正dfs重新进入void dfs(int u) { //u表示层数    if (u == n) { //当数填满n位数时  输出n位数 并且换行 for (int i = 0; i < n; i ++) {printf("%d ", path[i]); }  puts(""); return ;    }    for (int i = 1; i <= n; i ++) {  if (!st[i]) { //如果这个位置空的话（没有来过）     path[u] = i;     st[i] = true; //填数的时候记录一下     dfs(u + 1); //访问下一层     st[i] = false; //回溯的时候 恢复现场[] }    }}int main () {    cin >> n;    dfs(0); //这个题直接遍历    return 0;}

🌟三、AcWing 843. n-皇后问题

✨1.题目

题目链接

✨2、思路一

先讲原始方法，好理解一点，DFS按每个元素枚举 时间复杂度O(2的2ⁿ次幂)这个markdown语法确实不会有的兄弟教我一下，因为每个位置都有两种情况，总共有 n² 个位置
先看代码主要是dfs ,代码看不懂的话，往下看有图解

①、ac代码：

#include using namespace std;const int N = 20;//对角线元素 2n-1 取20防止越界 int n;char g[N][N]; //存储图 bool row[N],col[N], dg[N], udg[N]; //udg 副对角线 ///英语单词 column 列   diagonal 主角线 \ //row 行void dfs (int x,int y,int s) {  //xy为坐标 (x,y) s为 n皇后放置个数    if (y == n) { //当x走到行末尾的时候   y = 0;    //转到下一行的第一个 x++;    }    if (x == n) { //走到最后一行 且n皇后都放好的时候 if (s == n) { // 如果找到方案的话 for (int i = 0; i < n; i ++) {     puts(g[i]);//puts输出二维数组 输出每一行如何就会自动换行      }//puts遍历字符串这个语法不懂看下 puts(""); } return; //返回调用函数进行执行    }    dfs(x, y + 1, s);//不放皇后  并且访问右节点    // 判断皇后能否放在这格    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) { g[x][y] = 'Q';//放皇后 然后把 row[x] = col[y] = dg[x + y] = udg[x - y + n] = true; dfs(x , y + 1, s + 1);//放置皇后，找下一层的 //回溯的时候 记得恢复现场 ↓  row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;  g[x][y] = '.';    }}int main () {    cin >> n;    for (int i = 0; i < n;i ++) { for (int j = 0; j < n; j ++) {     g[i][j] = '.'; //初始化全部空格子 }    }    dfs(0,0,0); //从第一行开始找    return 0;}

②、代码剖析

主副对角线是线性代数的内容，看不懂的话自行百度

③、row数组的理解

④、dg[x + y] = udg[x - y + n]的理解

dg[x + y] = udg[x - y + n] 有的兄弟可能不理解其中x+y到底是什么意思？

以反对角线举例，x-y其实就是该点在对角线上的截距 由中学知识可知对角线方程为y = x + b，其中b表示截距也就是b = x - y（数组下标里面的东西）,如果在不同行，但再同一对角线，经过方程计算得到的截距都是一样的，不懂就拿纸自己写一下，+n是为了防止负数产生， 因为数组下标是不可能为负数的，因为每个数都+n，他们映射到结果是一样的，不信你就换个比n大的数试试。

✨3、思路二

这题和排列数字类似，算法效率比思路一高，主要是运用了剪枝算法;提前判断当前方案已经错误，不再继续往下搜索，提高算法效率

#include using namespace std;const int N = 20;//对角线元素 2n-1 取20防止越界 int n;char g[N][N]; //存储图bool col[N], dg[N], udg[N]; //udg 副对角线 ///英语单词 column 列   diagonal 主角线 \ void dfs (int x) {     if (x == n) { // 如果找到方案的话 for (int i = 0; i < n; i ++) {     puts(g[i]);//puts输出二维数组 输出每一行如何就会自动换行 } puts("");    return; //返回调用函数进行执行    }    /* puts语句不理解 可以看下面这个 作用是一样的 if (x == n) {     for (int i = 0; i < n; i ++) {  for (int j = 0; j < n; j ++) {      cout << g[i][j];  }  cout << endl;     }     cout << endl ;     return; }    */    //x:行  y:列    for (int y = 0; y < n; y ++) {     // 剪枝(提前判断当前方案已经错误，不再继续往下搜索，提高算法效率)  // 判断皇后能否放在这格   if (!col[y] && !dg[x + y] && !udg[n - x + y]) {     g[x][y] = 'Q';      col[y] = dg[x + y] = udg[n - x + y] = true;      dfs(x + 1);//找下一层的     //回溯的时候 记得恢复现场      col[y] = dg[x + y] = udg[n - x + y] = false;      g[x][y] = '.'; }    }}int main () {    cin >> n;    for (int i = 0; i < n;i ++) { for (int j = 0; j < n; j ++) {     g[i][j] = '.'; //初始化全部空格子 }    }    dfs(0); //从第一行开始找[0:下标]    return 0;}

🌟四、同类习题分享

洛谷P1562 点击跳转
洛谷P1219点击跳转

自己做一遍，我AC了，源代码需要找我

🌟五、结尾：

感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下🌹🌹🌹

K6漫画书在线商城