本文阅读事项：
1. 需要有一定基础：图、树的基本概念，递归，栈与队列。这些请在 OI Wiki\text{OI Wiki}OI Wiki 上自行学习。
2. 建议浅色阅读，效果更好。
3. 本文适合通过 GESP\text{GESP}GESP 4~5 级，准备学习 6~7 级内容，从算法入门过渡到算法中阶的或接触过基础算法的朋友阅读。
4. 为了让各位思路更清晰，这篇帖子只讲普通 DFS\text{DFS}DFS。本系列计划分为 4 篇帖子讲解，分别为：普通深搜、普通广搜、树上搜索、图上搜索。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
搜索
搜索，就是找一个东西，这个东西可以是抽象化的，也可以是具象的。它对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。想象一下，你是一只的老鼠，前面有一个洞穴，每个点都会有一些分叉，而只有一个地方放着粮食。你应该如何寻找这堆粮食呢？
基础搜索
深度优先搜索 DFS\TEXT{DFS}DFS 之思路
你是一只普通老鼠。最容易想到的策略是任意选择一条路，一直往前走，直到走不通了就退回来，再重新选择一条路。不断重复这个过程，就能找到粮食了。
这样“不撞南墙不回头“的思想，就是深度优先搜索（Depth-First Search,DFS）。对于深度优先搜索，官方的解释是：
> 为了求解，先寻找一种可能的方向搜索，遇到障碍就回溯，直到找到解或证明无解。
这段话比较抽象，直白来讲，就是一直朝着一个方向探索，没有路了就往回退，直到把所有可能都探索完。如下图，这就是 DFS\text{DFS}DFS 的基础搜索过程。
接下来讲解代码实现，各位可以先不往下翻，自己想想。
深度优先搜索 DFS\TEXT{DFS}DFS 之代码实现
深度优先搜索，肯定是往深入探索。那么，你一定会想到一个算法——递归！
没错，深搜可以用递归实现，也可以用栈实现。如果想了解栈的实现思路，可以自行查阅，这里讲解递归实现。但栈和递归本质上同宗同源，只不过一个用的系统栈，一个用的 STL 或数组栈而已。
递归的核心是枚举所有方向并深入搜索。但如果不加限制，可能会陷入死循环或重复计算。因此，DFS\text{DFS}DFS 引入标记数组 vis[] 来记录节点状态：
1. 剪枝：在进入节点前，若 vis[u] 为真，说明该节点在当前路径中已访问过（或全局已处理），直接跳过，避免重复搜索。
2. 回溯：对于需要枚举所有可行解的问题，在递归返回后，必须撤销当前节点的标记，以便该节点能出现在其他分支的路径中。这一点不理解没关系，待会的例题会讲到。
所以，基础的 DFS\text{DFS}DFS 大致有两种类型的题目：
* 迷宫问题（一维、二维），这类题目很明显是让你去搜索，比如迷宫寻路、救人等场景。
* 枚举可行解问题，要你枚举所有符合要求的解，没有明显的“搜索”之类的字眼，比如数字全排列。
我们来看一道例题：洛谷 P1706 全排列问题。
按照字典序输出自然数 111 到 n(1≤n≤9)n(1\le n\le 9)n(1≤n≤9) 所有不重复的排列，即 nnn 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。输出时每个数字保留 555 个场宽。
我们以 n=3n=3n=3 为例。可以想象有三个空，让你用 1,2,31,2,31,2,3 这三个数去填。首先，第一个空 1,2,31,2,31,2,3 都能选，假设我们填 111,那么将 111 标记为已选，不能再选。
第二个空只能选 2,32,32,3 了，填 222，那么 222 被标记为已选，不能再选。
第三个空只能填 333。
但是，这并不是唯一的填法。注意到，第二个空还可以填 333，这就需要回溯。这里要特别注意，因为之前 222 和 333 被标记为已访问了，所以退回到第二个空时，需要撤销 222 和 333 的已访问状态，这样它们才能在其他分支中被再次选择。
那么，后面的也是如此，就不一一演示了。最终，搜索出 666 种方案：
* 1,2,31,2,31,2,3
* 1,3,21,3,21,3,2
* 2,1,32,1,32,1,3
* 2,3,12,3,12,3,1
* 3,1,23,1,23,1,2
* 3,2,13,2,13,2,1
输出即可。
代码如下（C++）：
不难发现，这种题是枚举可行解问题，这类题目还有P2105 K皇后，P1219 [USACO1.5] 八皇后 Checker Challenge，B3622 枚举子集（递归实现指数型枚举）等等。
那么，这类题的模版可以归类为（C++ 伪代码）：
接下来，我们看另一个例题：洛谷 B3625 迷宫寻路。
从 (1,1)(1,1)(1,1) 出发，只能上下左右移动，. 为空地，#是障碍，是否可以到 (n,m)(n,m)(n,m)。能到输出 Yes，否则输出 No。1≤n,m≤1001\le n,m\le 1001≤n,m≤100。
这道题是一个典型的迷宫连通性问题。由于只需要判断“是否可达”，而不需要求出最短路径或具体路径，因此我们不需要回溯（即不需要在递归返回时取消标记）。一个格子一旦走过，就不需要再走第二次，因为再次走到该点并不会带来新的信息。
我们可以引入 dx[],dy[] 数组，他们表示下一步（上下左右）的 x,yx,yx,y 坐标偏移了多少，也叫做偏移量。不难发现，当前位置 (x,y)(x,y)(x,y) 上下左右的坐标如下图：
这几个位置的偏移量如下图：
所以，dx[]的值可以为 {0,0,-1,1}，dy[]的值为 {-1,1,0,0}。注意，偏移量数组作用是帮助我们快捷的计算出下一步的下标，所以，dx[i] 一定要和 dy[i] 一一对应，否则就会计算错误。注意，偏移量数组不唯一，只需要一一对应即可。
比如，i = 1时，dx[1]=-1,dy[1]=0，对应向左。只需要将原下标加上偏移量即可，即
nx=x+dxi,ny=y+dyinx=x+dx_i,ny=y+dy_i nx=x+dxi ,ny=y+dyi
其中，iii 表示方向值，x,yx,yx,y 为当前坐标，nx,nynx,nynx,ny 为新坐标（new x,new y\text{new x,new y}new x,new y）。
一些细节会在代码里讲：代码如下（C++）：
同样的题目有：P1135 奇怪的电梯，P6566 [NOI Online #3 入门组] 观星，P1141 01迷宫等等。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
那么，基础 DFS\text{DFS}DFS 就全部讲完了，希望 @AC君 加精，各位点赞。
小彩蛋：DFS\text{DFS}DFS = 电风扇 = 巅峰赛 = 等方式 = 的方式 = 大丰收 = 对方说。你打“dfs”的第一个词是什么？（我是大丰收）
