[算法笔记] DFS搜索
\(\text {DFS}\) 深度优先搜索
深度优先搜索，简称\(\text {DFS}\)（\(\text {Depth First Search}\)），顾名思义，就是搜索时的深度优先。
\(\text {DFS}\) 的本质其实是暴力枚举，只不过 \(\text {DFS}\) 在枚举时会检测当前枚举的选项是否符合条件，
如果符合，保存此选项，枚举下一个选项；反之更换一个选项，尝试此选项是否合法；但如果此时
发现没有可枚举的选项了，也就是所有的选项有不合法，进行「回溯」操作，更换上一个选项。
这样，枚举时就可以避免枚举许多无效的状态，以此节省时间。
可以举一个这样的例子：\(\text {DFS}\) 是一个有点智慧的人，他会想想自己干的事情有没有意义，
没有的话就放弃这个事情；
而枚举就是一个老实的人，他会老老实实的把所有活都干完，但却不知道自己干了一堆
没有意义的事。
刚刚所说 \(\text {DFS}\) 其实是图论中的一个概念。在搜索中常常指回溯算法，它们之间的关系在此不多说明，
只需知道 \(\text {DFS}\) 是一种搜索的算法即可。
\(\text {DFS}\) 的常见形式如下
void dfs(当前枚举到的选项){
if(所有的状态都枚举完毕){
输出/保存结果
return;
}
for(枚举当前选项)
if(这个选项是合法的){
记录这个选项
dfs(下一层枚举的状态);
取消这个选项
}
}
给定一个 \(N \times M\) 方格的迷宫，迷宫里有 \(T\) 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标 \(SX,SY\) 和终点坐标 \(FX,FY\)，每个障碍物的 \(X,Y\)，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
\(N \le M \le 5\)
这题我们可以枚举移动的方向，记录，再判断路上有没有障碍物，很明显时间允许，可以 \(\color {green} {\texttt {AC}}\)，但要是 \(N \le M \le 30\) 呢？
这时，我们就可以使用 \(\text {DFS}\) 了。
我们枚举上下左右四个方向，同时判断移动的方向有没有障碍物和有没有走过，分别用 \(a\) 和 \(note\) 记录，
再用一个 \(sum\) 记录解的数量，用 \(x,y\) 记录当前 \(dfs\) 枚举到的位置，代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,t,fx,fy,sx,sy,sum;
int a[6][6],note[6][6],next1[5][2] = {{114514,1919810},{0,1},{1,0},{0,-1},{-1,0}}; // 存储地图和走过的位置
void dfs(int x,int y){
if(x == fx && y == fy){ // 如果到了终点
sum ++; // 记录解的数量
return;
}
for(int i = 1;i <= 4;i ++){ // 枚举方向
int next_x = x + next1[i][0],next_y = y + next1[i][1]; // 计算下一步的坐标
if(!a[next_x][next_y] && !note[next_x][next_y]){ // 如果没有障碍物且也没走过
note[next_x][next_y] = 1; // 标记为走过
dfs(next_x,next_y); // 继续走迷宫
note[next_x][next_y] = 0; // 走完后恢复，方便下一次枚举
}
}
}
int main(){
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(int i = 1;i <= t;i ++){
int x,y;
cin>>x>>y;
a[x][y] = 1;
} // 以上为输入
a[sx][sy] = 1; // 标记起点为障碍物，防止无限来回
for(int i = 0;i <= n + 1;i ++)
for(int j = 0;j <= m + 1;j ++)
if(i == 0 || i == n + 1 || j == 0 || j == m + 1)a[i][j] = 1; // 标记边缘为障碍物
dfs(sx,sy); // go,go,go！开始走迷宫
cout<<sum; // 输出解的数量
return 0; // 完结撒花
}
完美 \(\color {green} {\texttt {AC}}\)！\(\text {DFS}\) 太厉害了吧！
但还记得我说的吗？\(\text {DFS}\) 只是个有点智慧的人，如果有一个迷宫，但是它有许多岔路口，
而且它有一个超级长的死胡同，会怎样？很明显，\(\text{DFS}\) 越走越深，最后在大量的回溯枚举中 \(\texttt {TLE}\)……
也就是说，\(\text {DFS}\) 是「不撞南墙不回头」，不遇到非合法情况他就会一直走下去，有的时候真的会有问题……
这时，\(\text {BFS}\) 就该出场了。
欲知后事如何，且看下回分解。