少年Q

用户名：yin19990129

访问量：25370

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

53.最短路练习-题解(C++代码)只做最好的思路！
浏览：164

[传智杯]软件工程实习（C++描述）只做最好的思路！
浏览：380

[传智杯]程序员节发橙子（C++描述）只做最好的思路！
浏览：487

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

40.殊途同归（C++代码）只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-04-09 18:50:33 浏览：508　|　评论：0　

原题链接：殊途同归

这题的确是怪折腾人的，一开始我竟然一点都不会，主要是bfs接触的太少了，老师傅也没给代码，后来只能参考大神的代码，研究了半天终于能自己码出bfs了，这题大家可以作为一个模板，以后用到bfs的时候可以参照这个模板，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
char a[6][6];
int d[10][10];
int f[10][10];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int sx=1,sy=1,gx,gy;
const int inf=100000;
typedef pair<int,int>p;
pair<int,int>q;
int bfs(){
	int nx,ny;
	queue<p>que;
	que.push(p(sx,sy));
	d[sx][sy]=0;
	f[sx][sy]=1;
	while(que.size()){
		q=que.front();
		que.pop();
		if(q.first==gx&&q.second==gy){
			break;
		}
		for(int i=0;i<4;i++){
			nx=q.first+dx[i];
			ny=q.second+dy[i]; 
			if(1<=nx&&nx<=5&&1<=ny&&ny<=5&&a[nx][ny]!='*'){
				f[nx][ny]+=f[q.first][q.second];
				if(d[nx][ny]==inf){
					d[nx][ny]=0;
					que.push(p(nx,ny));
				}
			}
		}
	}
	return f[gx][gy];
}
int main(){
	int ans;
	for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			cin>>a[i][j];
			if(a[i][j]=='S'){
				gx=i;
				gy=j;
			}
			d[i][j]=inf;
		}
	}
	ans=bfs();
	cout<<ans<<endl;
	return 0;
}
```
关于bfs的几点补充:
广度优先算法（Breadth-First-Search），简称BFS，是一种图形搜索演算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标则演算终止。
BFS是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
时间复杂度：邻接表的时候是O(|V| + |E|)。其中 |V| 是节点的数目，|E| 是图中边的数目。
适用条件：对于所有边长度相同的情况，比如地图的模型，bfs第一次遇到目标点，此时就一定是从根节点到目标节点最短的路径（因为每一次所有点都是向外扩张一步，你先遇到，那你就一定最短）。bfs先找到的一定是最短的。但是如果是加权边的话这样就会出问题了，bfs传回的是经过边数最少的解，但是因为加权了，这个解到根节点的距离不一定最短。比如1000+1000是只有两段，1+1+1+1有4段，但是bfs返回的经过边数最少的解，这里总长度2000，显然不是最短的路径。此时我们就应该采用Dijkstra最短路算法解决加权路径的最短路了。
其他补充：
typedef pair<int,int> p;
pair<int,int>q;
c++里的pair用法补充：
pair是将2个数据组合成一个数据，当需要这样的需求时就可以使用pair，如STL中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一种结构体，主要的两个成员变量是first, second 因为是使用struct不是class，所以可以直接使用pair的成员变量。

此外，网友还给出了这题的dfs题解版本，代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 100000000;
int minS = INF;
int a[100],n = 5;
char G[30][30];
bool visited[30][30];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
void DFS(int i,int j,int step){
//    visited[i][j] = true;
    if(G[i][j] == 'S'){
        if(step<=minS){   //找最小的步数,有多种相同的情况，所以要小于或等于
            minS = step;
            a[minS]++;
        }
        return;
    }
    visited[i][j] = true;
    for(int k = 0;k<4;k++){            //四个方向
        int nx = i+dx[k];
        int ny = j+dy[k];
        if(0<=nx&&nx<n && 0<=ny&&ny<n && G[nx][ny]!='*' && !visited[nx][ny]){
            visited[nx][ny] = true;        //标记访问
            DFS(nx,ny,step+1);            //dfs
            visited[nx][ny] = false;    //回溯
        }
    }
}
int main(){
    int i,j;
    for(i = 0;i<n;i++)
        for(j = 0;j<n;j++){
            cin>>G[i][j];
        }
    DFS(0,0,0);
//    cout<<minS<<endl;
    for(int i = 0;i<100;i++){
        if(a[i]>0){
            cout<<a[i]<<endl;
            break;
        }
    }
    return 0;
}
```
有关bfs和dfs的区别和不同情况下的使用情况：
什么时候用DFS，什么时候用BFS?
二维数组的题目，N小于20的，适用DFS。而一般 N<= 200，N<=1000这种，一定不可能用DFS去做。而且并不只是整个题目不能用DFS，其中的每一步也不能使用DFS。
BFS的基本步骤
1.将初始点（一个或多个）加入一个集合尾
2.从集合头取出点，判断初始点的周边点，将符合条件的点加入队列
3.重复2操作，直至集合为空。(一般每个点只加入队列一次)
一般来说用DFS解决的问题都可以用BFS来解决。
DFS(深搜的同时考虑回溯）
bfs＝队列，入队列，出队列；dfs=栈，压栈，出栈
bfs是按一层一层来访问的，所以适合有目标求最短路的步数，你想想层层搜索每次层就代表了一步。bfs优先访问的是兄弟节点，只有这一层全部访问完才能访问下一层，也就是说bfs第几层就代表当前可以走到的位置(结点).而dfs是按递归来实现的，它优先搜索深度，再回溯，优先访问的是没有访问过的子节点
DFS多用于连通性问题因为其运行思想与人脑的思维很相似，故解决连通性问题更自然。BFS多用于解决最短路问题，其运行过程中需要储存每一层的信息，所以其运行时需要储存的信息量较大，如果人脑也可储存大量信息的话，理论上人脑也可运行BFS。
总的来说多数情况下运行BFS所需的内存会大于DFS需要的内存(DFS一次访问一条路，BFS一次访问多条路)，DFS容易爆栈(栈不易"控制")，BFS通过控制队列可以很好解决"爆队列"风险。
它们两者间各自的优势需要通过实际的问题来具体分析，根据它们各自的特点来应用于不同的问题中才能获得最优的性能。

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

少年Q

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

40.殊途同归（C++代码）只做最好的思路！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

【明明的随机数】（C++代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

The 3n + 1 problem （C语言代码）

1054题解

小九九（C语言描述,不看要求真坑爹）

分糖果（C语言代码）

时间转换（C语言代码）

少年Q

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

40.殊途同归 （C++代码）只做最好的思路！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

【明明的随机数】 （C++代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

The 3n + 1 problem （C语言代码）

1054题解

小九九 （C语言描述,不看要求真坑爹）

分糖果 （C语言代码）

时间转换 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

40.殊途同归（C++代码）只做最好的思路！

　　评论区

【明明的随机数】（C++代码）

小九九（C语言描述,不看要求真坑爹）

分糖果（C语言代码）

时间转换（C语言代码）