深度优先搜索（dfs）与广度优先搜索（bfs）
深度优先搜索（dfs）
1.深度优先搜索的原理
深度优先搜索，顾名思义，搜到底才退回来，我们可以这么比喻：
这里有一个迷宫，
你会怎么走？是不是直接直走，然后右转？但深度优先搜索不是这样的
它会先走最近的一条路，然后走到底，这里发现走不了，再退出来
然后走另一条道，发现还是不行，在退回转角处
退回来后，发现两条路都走不了，那么在后退
然后按这条路一直走就能到了！
所以深度优先搜索的原理是：不撞南墙不回头！
2.深度优先搜索的代码
1.东方博宜p1434 数池塘
1434 - 数池塘（四方向）
题目描述
农夫约翰的农场可以表示成 N×M个方格组成的矩形。由于近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者有积水（W）或者没有积水（.）。
农夫约翰打算数出他的农场上共形成了多少池塘。一个池塘是一系列相连的有积水的方格，每一个方格周围的四个方格都被认为是与这个方格相连的。现给出约翰农场的图样，要求输出农场上的池塘数。
输入
第 1行：由空格隔开的两个整数：N 和 M；
第 2…N+1 行：每行 M 个字符代表约翰农场的一排方格的状态。每个字符或者是W或者是.，字符之间没有空格。
数据范围
1≤N,M≤1001≤N,M≤100。
输出
输出只有1行，输出约翰农场上的池塘数。
样例
输入
复制
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.
输出
复制
13
#include<bits/stdc++.h> using namespace std; int n,m,sum=0; int dx[4]={0,0,1,-1};//方向数组 int dy[4]={1,-1,0,0}; char a[101][101]; void dfs(int x,int y){ a[x][y]='.';//发现是就变成. for(int i=0;i<4;i++){ int nx=x+dx[i]; int ny=y+dy[i]; if(a[nx][ny]=='W' && nx>=1 &&nx<=n && ny>=1 && ny<=m){//如果是池塘，那么就继续搜 dfs(nx,ny); } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='W'){ dfs(i,j); sum++; } } } cout<<sum; return 0; }2.洛谷p1451求细胞数量
# P1451 求细胞数量
## 题目描述
一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
## 输入格式
第一行两个整数代表矩阵大小 $n$ 和 $m$。
接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 `0` 到 `9` 的字符串，代表这个 $n \times m$ 的矩阵。
## 输出格式
一行一个整数代表细胞个数。
## 输入输出样例 #1
### 输入 #1
```
4 10
0234500067
1034560500
2045600671
0000000089
```
### 输出 #1
```
4
```
## 说明/提示
#### 数据规模与约定
对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$。
网址为P1451 求细胞数量 - 洛谷，可自行查看
#include<bits/stdc++.h> using namespace std; int n,m,ans=0; char a[101][101]; int b[4]={0,0,1,-1};//依旧方向数组 int c[4]={-1,1,0,0}; void dfs(int x,int y){ a[x][y]='0'; for(int i=0;i<4;i++){ int nx=x+b[i]; int ny=y+c[i]; if(a[nx][ny]!='0' && nx>=1 && nx<=n && ny>=1 && ny<=m){ dfs(nx,ny); } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]!='0'){ dfs(i,j); ans++;//如果是0就加，不管旁边有多少个 } } } cout<<ans; return 0; }温馨提示：数据量太大不会怎么样不·可以食用！
广度优先搜索（bfs）
又名宽度优先搜索，考试的时候不许错
1.广度优先搜索的原理
依旧看图
我们给每个都标上序号，自上向下，从左向右
为1,2，3,4,5,6,7
他会先搜到2和3，然后就不要1了[笑脸]
接着搜到4,5,6,7的时候就不要2和3了
宽度优先搜索的原理：忘恩负义
只要你有苹果15，就不用苹果14了
温馨提示：不能浪费东西哦！
2.广度优先搜索的代码（队列）
我给大家的是队列的写法，没有写二维的，因为我不会
1.洛谷b3626
# B3626 跳跃机器人
## 题目描述
地上有一排格子，共 $n$ 个位置。机器猫站在第一个格子上，需要取第 $n$ 个格子里的东西。
机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：
- 初始时，机器人位于 $1$ 号格子
- 若机器人目前在 $x$ 格子，那么它可以跳跃到 $x-1, x+1, 2x$ 里的一个格子（不允许跳出界）
问机器人最少需要多少次跳跃，才能到达 $n$ 号格子。
## 输入格式
仅一行，一个正整数，表示 $n$。
## 输出格式
仅一行，一个正整数，表示最少跳跃次数。
## 输入输出样例 #1
### 输入 #1
```
30
```
### 输出 #1
```
6
```
## 输入输出样例 #2
### 输入 #2
```
50
```
### 输出 #2
```
7
```
## 输入输出样例 #3
### 输入 #3
```
64
```
### 输出 #3
```
6
```
## 输入输出样例 #4
### 输入 #4
```
63
```
### 输出 #4
```
8
```
## 说明/提示
#### 样例解释
第一组样例：
$1\to 2 \to 4\to 8 \to 16 \to 15 \to 30$
第二组样例：
$1\to 2\to 3\to6\to12\to24\to25\to 50$
第三组样例：
$1\to 2\to4\to8\to16\to32\to64$
第四组样例：
$1\to 2\to4\to8\to16\to32\to31\to62\to63$
请注意在本组样例中，$63$ 不能通过 $64-1$ 得到，因为格子总数为 $63$，没有第 $64$ 个格子。
#### 数据规模与约定
对于 $100\%$ 的数据，有 $1\leq n \leq 10^6$。
网址：B3626 跳跃机器人 - 洛谷
解法：
#include<bits/stdc++.h> using namespace std; int n; int a[1000001]; queue <int>q;//定义队列 void bfs(){ q.push(1);//添加1（初始地点） while(!q.empty()){//不为空 int t=q.front(); q.pop();//刚才图中删除的代码 if(t+1<=n&&a[t+1]==-1){ a[t+1]=a[t]+1; q.push(t+1);//更改 } if(t-1>0&&a[t-1]==-1){ a[t-1]=a[t]+1; q.push(t-1);//更改 } if(t*2<=n&&a[t*2]==-1){ a[t*2]=a[t]+1; q.push(t*2);//更改 } } } int main(){ memset(a,-1,sizeof(a)); cin>>n; a[1]=0; bfs(); cout<<a[n]; return 0; }2.洛谷P1135 奇怪的电梯
# P1135 奇怪的电梯
## 题目背景
感谢 @[yummy](https://www.luogu.com.cn/user/101694) 提供的一些数据。
## 题目描述
呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼（$1 \le i \le N$）上有一个数字 $K_i$（$0 \le K_i \le N$）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：$3, 3, 1, 2, 5$ 代表了 $K_i$（$K_1=3$，$K_2=3$，……），从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？
## 输入格式
共二行。
第一行为三个用空格隔开的正整数，表示 $N, A, B$（$1 \le N \le 200$，$1 \le A, B \le N$）。
第二行为 $N$ 个用空格隔开的非负整数，表示 $K_i$。
## 输出格式
一行，即最少按键次数，若无法到达，则输出 `-1`。
## 输入输出样例 #1
### 输入 #1
```
5 1 5
3 3 1 2 5
```
### 输出 #1
```
3
```
## 说明/提示
对于 $100 \%$ 的数据，$1 \le N \le 200$，$1 \le A, B \le N$，$0 \le K_i \le N$。
本题共 $16$ 个测试点，前 $15$ 个每个测试点 $6$ 分，最后一个测试点 $10$ 分。
网址为：P1135 奇怪的电梯 - 洛谷
#include<bits/stdc++.h> using namespace std; int n,a,b; int dx[201]; int m[201]; queue <int>q; void bfs(){//与上题一模一样的模版 q.push(a); while(!q.empty()){ int t=q.front(); q.pop(); if(m[t+dx[t]]==-1&&t+dx[t]<=n){ m[t+dx[t]]=m[t]+1; q.push(t+dx[t]); } if(m[t-dx[t]]==-1&&t+dx[t]>=1){ m[t-dx[t]]=m[t]+1; q.push(t-dx[t]); } } } int main(){ memset(m,-1,sizeof(m));//清空数组 cin>>n>>a>>b; for(int i=1;i<=n;i++){ cin>>dx[i]; } m[a]=0; bfs(); if(a==b){ cout<<0; } else cout<<m[b]; return 0; }3.洛谷p1143 马的遍历
一道二维的板子题
#include<bits/stdc++.h> using namespace std; int p1,p2,q1,q2; int a[401][401]; struct zzz{ int i,j,s=0;//存储坐标 }; queue <zzz>q; //熟悉的方向数组 int dx[9]={-1,1,2,2,1,-1,-2,-2}; int dy[9]={-2,-2,-1,1,2,2,1,-1}; void bfs(){ zzz j; j.i=q1; j.j=q2; q.push(j); while(!q.empty()){//熟悉的流程 j=q.front(); q.pop(); for(int i=0;i<8;i++){ int nx=dx[i]+j.i; int ny=dy[i]+j.j; if(a[nx][ny]==-1&&nx>=1&&nx<=p1&&ny>=1&&ny<=p2){ zzz c; c.i=nx; c.j=ny; c.s=j.s+1; a[nx][ny]=c.s; q.push(c); } } } } int main(){ cin>>p1>>p2>>q1>>q2; memset(a,-1,sizeof(a)); bfs(); a[q1][q2]=0; for(int i=1;i<=p1;i++){ for(int j=1;j<=p2;j++){ cout<<a[i][j]<<' '; } cout<<endl; } return 0; }总结
原理
深度优先搜索：不撞南墙不回头
广度优先搜索（宽度优先搜索）：只要你有苹果15，就不用苹果14了//无意冒犯
优劣处：
深度优先搜索怕数据大
广度优先搜索太烧脑
本期就到这里了，我们下次再见！[微笑]