深度优先搜索（dfs）与广度优先搜索（bfs）
深度优先搜索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$。
解法：
#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了//无意冒犯
优劣处：
深度优先搜索怕数据大
广度优先搜索太烧脑
本期就到这里了，我们下次再见！[微笑]
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
10
0- 0
已为社区贡献1条内容
所有评论(0)