JakeLin

用户名：jake546

访问量：43187

签　名：

腾讯需要我！

等　　级
排　　名	40
经　　验	13199
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-1745题-继续畅通工程-题解(C++代码)-简单易懂
浏览：314

JakeLin-1729题-还是畅通工程-题解(C++代码)-简单易懂
浏览：292

JakeLin-2313题-[传智杯]软件工程实习-题解(C++代码)-结构体排序
浏览：289

你可能喜欢

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

迷宫问题-题解(C/C++)-BFS（附图详细解析）

　　作者: JakeLin　　　　发表时间：2020-02-06 16:02:18 浏览：1652　|　评论：1　

原题链接：迷宫问题

> 本道题是迷宫问题，这里使用BFS（广度优先遍历）求解

- 需先理解BFS：
**图的BFS（广度优先遍历）可以理解为树的遍历中的层次遍历，它是从起点开始向外一层一层遍历的，如下图：**
![](/image_editor_upload/20200206024623_24420.jpg)
遍历方法有模板可循：
```cpp
    1.建立一个队列
    2.访问起始节点，将起始节点入队
    3.while(队中还有元素){
    	访问队首的领接节点，并将它们入队（需是没有访问过的）；
		队首出队；
    }
    //直到队列为空循环结束
```
- 解释结构体节点node
```cpp
struct node{
	int x,y,d;
	node(int a,int b,int c){
		x=a;
		y=b;
		d=c;
	}
};
```
其中，

|  （x,y） |  表示当前节点的横纵坐标 |
| ------------ | ------------ |
|  h  | 为步数（初始为0），可以理解为层数，数值是层数减1，当前节点的层数是**上一层节点（出队那个节点）**的层数+1  |
|  node（a,b,c） |  带参的构造函数 |

- 如何遍历邻接节点

假设节点的相邻节点有四个方向："D","L","R","U"
本题我使用两个数组来遍历四个方向
> int dr[] = {0,0,-1，1};  //x轴移动
int dc[] = {-1,1,0，0};  //y轴移动

i为0~3时，分别表示"L","R","U"，"D"；
例如i=0时，x+0，y+（-1）表示横坐标方向不变，纵坐标方向下移，即为“L”：向左一个单位

------------

附完整代码如下：
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 100 + 10;
struct node{
	int x,y,d;
	node(int a,int b,int c){
		x=a,y=b,d=c;
	}
};
char map[maxn][maxn];
int vis[maxn][maxn];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int n,m;
bool bfs(int x,int y){
	queue<node> q;
	vis[x][y]=1;
	node start = node(x,y,0);
	q.push(start);
	while(!q.empty()){
		node u = q.front();
		q.pop();
		int ux = u.x;
		int uy = u.y;
		int ud = u.d;
		if(map[ux][uy]=='E'){
			cout<<ud<<endl;
			return true;
		}
		for(int i=0;i<4;i++){
			int newx = ux + dx[i];
			int newy = uy + dy[i];
			int newd = ud + 1;
			if(newx<n && newx>=0 && newy<m && newy>=0
			&& vis[newx][newy]==0
			&& map[newx][newy]!='#'){
				vis[newx][newy]=1;
				q.push(node(newx,newy,newd));
			}
		}
	}
	return false;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		memset(vis,0,sizeof(vis));
		int sx,sy;
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++){
			scanf("%s",&map[i]);
			for(int j=0;j<m;j++){
				if(map[i][j]=='S'){
					sx=i;
					sy=j;
				}
			}
		}
		if(!bfs(sx,sy)){
			cout<<"-1"<<endl;
		}
	} 
	return 0;
}

```
一起努力，如果觉得有用，请为我点个评分:innocent:~

0.0分

23 人评分

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

　　评论区

汝顾

大佬，膜拜

2020-07-02 14:05:40

JakeLin

TA的其他文章

你可能喜欢

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

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

弟弟的作业（C语言代码）

用筛法求之N内的素数。（C语言代码）

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

迷宫问题-题解(C/C++)-BFS（附图详细解析）

评论区

精彩推荐

C二级辅导-等差数列（C++代码）

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

A+B for Input-Output Practice (V) （C++代码）

最长单词（C语言代码）

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

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

C语言训练-求函数值（C语言代码）

printf基础练习2 （有点不明白）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

求圆的面积（C语言代码）

JakeLin

TA的其他文章

你可能喜欢

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

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

弟弟的作业 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

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

迷宫问题-题解(C/C++)-BFS（附图详细解析）

评论区

精彩推荐

C二级辅导-等差数列 （C++代码）

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

A+B for Input-Output Practice (V) （C++代码）

最长单词 （C语言代码）

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

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

C语言训练-求函数值 （C语言代码）

printf基础练习2 （有点不明白）

WU-蓝桥杯算法提高VIP-勾股数 （C++代码）

求圆的面积 （C语言代码）

弟弟的作业（C语言代码）

用筛法求之N内的素数。（C语言代码）

　　评论区

C二级辅导-等差数列（C++代码）

最长单词（C语言代码）

C语言训练-求函数值（C语言代码）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

求圆的面积（C语言代码）