dfs 搜索讲解
Fubaogege
·
·
学习·文化课
今天我们来聊聊关于 dfs（深搜）的思路。
思路部分
首先，dfs 分为 4 个大部分。分别是抵达目标，枚举前进方向与判断，搜索部分和回溯。
抵达目标
顾名思义，搜索目标就是抵达边界，当你到达一个边界，就是到达终点，你要干一件事。具体是什么取决于题目。
判断能不能到达终点，能到达输出 `Yes`，不能到达输出 `No`。这时，到达终点（抵达边界）我们要做的是就是输出 `Yes` 因为到达了终点，最后用 `exit(0)` 强制结束程序（因为已经输出了 `Yes` 程序结束了）。
计算到达方法，这是我们要做的事是 `ans++` 因为我们到达了终点，所以这条路可行（又多了一条可行的路），所以 `ans++`，不用担心重复问题，因为让 `i++` 的 `for` 循环不会 `i--` 也就是搜索原来的已经搜索过的路径。
计算最短或最多路径，没路输出 `-1`，这时又有两种情况（有很多种方法中的一种，最好理解的）：
最短：
定义变量 `mina` 不是 `min`，这里应该都知道，因为 `min` 已经是被定义的函数了。首先将初始值设为 `最大值+1` 普遍都是 $n \times m + 1$，为什么要 $+1$ 呢，因为 $n \times m$ 是可以达到的，就不能使后面的输出 `-1` 的判断成立，因为输出 `-1` 是因为没有路径可达到，所以输出的 `-1`，话说刚才， $n \times m$ 是可以达到的，而 $n \times m + 1$ 是不可以达到的，所以定义 `mina` 的程序是：`int mina=n*m+1;`，而到达边界更新的程序是 `mina=min(mina,ans)`，如果 `mina` 最后没变，代表没有路径可达到，输出 `-1`。
最长：
定义变量 `maxa` 不是 `max`，这里应该都知道，因为 `max` 已经是被定义的函数了。首先将初始值设为 `-1`，简单解释成：让他每次有新的路径就能更新，而没人可以走 `-1` 步，所以初始值设为 `-1`，而到达边界更新的程序是 `maxa=max(maxa,ans)`，如果 `maxa` 最后没变，代表没有路径可达到，输出 `-1`。
## 枚举前进方向与判断
这里只讲普遍的题目（四个方向的）。
搜索和递归差不多，都是拆分成小的部分，这里小的部分是**单个坐标**。
四个方向分别是：
- 上，`dx-1,dy`（行数 $-1$）;
- 下，`dx+1,dy`（行数 $+1$）;
- 左，`dx-1,dy`（列数 $-1$）;
- 右，`dx-1,dy`（列数 $+1$）;
定义变量：
```c
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
```
因为是枚举，我们把每个方向都试一遍，用 `for` 循环：
`for(int i=0;i<4;i++){;}`
因为变量的下标是是从 $0$ 开始的，所以 `for` 循环为 $0 \sim 3$。
判断：
先**预冥想**一下下一个的坐标：
`int xx=x+d[i],dy=y+d[y];`
灵魂三连问（三个不能走的地方），这里将简单点：
- 边界，超过边界不能走。
`if(xx<1||yy<1||xx>n||yy>m)return ;`。
- 墙不能走。
`if(c[xx][yy]=='#")return ;`。
- 走过不能走。
`if(vis[xx][yy]==1) return ;`。
剩下的就是能走的。
## 搜索部分
续接上一个部分的思路：“剩下的就是能走的。”
因为能走了，我们可以让他走了，但是要将 `vis` 变成 $1$ 因为他走过了，要打**标记**。
`vis[xx][yy]=1`。
接下来让他走。
`dfs(xx,yy);`
因为这个地方可以走。
## 回溯
回溯是因为实在走到了死胡同，走不了了，但是有的程序最好不加回溯，在这里我们来讨论一下：
因为不走了，所以抹除标记，抹除所有的记录，因为根本就没走过。
`vis[xx][yy]=0`。
因为有些题目有**步数**：
又是两种情况：
- 全局变量，自己写回溯。
- 形式参数，自带回溯，不用写。
到这里整个 dfs 部分就讲完了，最后是重点难点和模版。
## 重点
一：“灵魂三连问”的用不用：
我们已知，灵魂三连问的具体的是指：**走没走过**，**到没到边界**和**能不能走**。
- **走没走过**：我们通常遇到的题目都是只能走一次，求最短路径，所以不能重复的走。
- **到没到边界**：就以我们最具代表性的**棋盘问题**来讲，棋盘是有边界的，在一个 $11\times11$ 的棋盘里我们不能走到 $(12,12)$ 这个坐标，所以，棋盘外的东西也是不能走的。
- **能不能走**：我们基本上是满足一个条件就不能走了，这里可以是步数用光了，也可以是墙。
## 模版
```c
void dfs(int x,int y,int bs){
if(x==n&&y==m){
//抵达边界
}
for(int i=0;i<4;i++){//枚举
//预冥想
//灵魂三连问（能不能走）
//递归与回溯
}
}
```