JakeLin

用户名：jake546

访问量：38479

签　名：

腾讯需要我！

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

　　自我简介：

幸福是奋斗出来的

TA的其他文章

[算法提高VIP]分分钟的碎碎念（C++代码）两种方法：DP与暴力
浏览：405

蓝桥杯2013年第四届真题-带分数-题解(C++代码) 全排列
浏览：573

数列问题-题解(C++代码) 数组
浏览：336

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

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

　　作者: JakeLin　　　　发表时间：2020-02-06 16:02:18 浏览：1450　|　评论：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分

22 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

汝顾

大佬，膜拜

2020-07-02 14:05:40

JakeLin

TA的其他文章

你可能喜欢

弟弟的作业（C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

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

C语言训练-舍罕王的失算（C语言代码）

C语言考试练习题_保留字母（C语言代码）

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

评论区

精彩推荐

蓝桥杯历届试题-九宫重排（C++代码）

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

水仙花（C语言代码）

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

数对（C语言代码）

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

简单的a+b （C语言代码）

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

众数问题（C语言代码）

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

JakeLin

TA的其他文章

你可能喜欢

弟弟的作业 （C++代码）

C语言程序设计教程（第三版）课后习题6.11 （C++代码）（有个库函数叫sqrt）

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

C语言训练-舍罕王的失算 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

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

评论区

精彩推荐

蓝桥杯历届试题-九宫重排 （C++代码）

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

水仙花 （C语言代码）

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

数对 （C语言代码）

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

简单的a+b （C语言代码）

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

众数问题 （C语言代码）

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

弟弟的作业（C++代码）

C语言训练-舍罕王的失算（C语言代码）

C语言考试练习题_保留字母（C语言代码）

　　评论区

蓝桥杯历届试题-九宫重排（C++代码）

水仙花（C语言代码）

数对（C语言代码）

众数问题（C语言代码）