JakeLin-题解1923：蓝桥杯算法提高VIP-学霸的迷宫（C++代码）

1167 阅读 8 评论 0 点赞

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

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

|  （x,y） |  表示当前节点的横纵坐标 |
| ------------ | ------------ |
|  h  | 为步数（初始为0），可以理解为层数，数值是层数减1，当前节点的层数是**上一层节点（出队那个节点）**的层数+1  |
|  s | 表示从起始点走到当前点路径的字符串，当前节点的路径是**上一层节点的路径（出队那个节点）**再加上一个它们之间的移动字母  |
|  node（a,b,c） |  带参的构造函数 |

- 多条路径符合条件的情况
> 题目要求：有多条路径符合条件，选择字典序最小的题目要求：有多条路径符合条件，选择字典序最小的

这要求我们在遍历出队节点的邻接节点时的顺序应为："D","L","R","U"
本题我使用两个数组来遍历四个方向
> int dr[] = {1,0,0,-1};  //x轴移动
int dc[] = {0,-1,1,0};  //y轴移动

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

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

附完整代码如下：
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 500 + 10;
struct node{
	int x,y,h;
	string s;
	node(int a,int b,int c){
		x=a;
		y=b;
		h=c;
		s="";
	}
};
char map[maxn][maxn];
int vis[maxn][maxn];
int dr[] = {1,0,0,-1};
int dc[] = {0,-1,1,0};
string d[] = {"D","L","R","U"};
int n,m;
int h=0;
int hx,hy;
char res[maxn];
int cnt=0;
bool bfs(int x,int y){
	vis[x][y]=1;
	queue<node> q;
	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 uh = u.h;
		string us = u.s;
		if(ux==n-1 && uy==m-1){  //结束条件 
			cout<<uh<<endl<<us;
			return true;
		}
		for(int i=0;i<=3;i++){
			int newx = ux + dr[i];
			int newy = uy + dc[i];
			int newh = uh + 1;
			if(newx<n && newx>=0 && newy<m && newy>=0
			&& vis[newx][newy]==0
			&& map[newx][newy]=='0'){
				vis[newx][newy]=1;
				node newn = node(newx,newy,newh);
				newn.s = us + d[i];
				q.push(newn);
			}
		}
	}
	return false;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",&map[i]);
	}
	bfs(0,0);
	return 0;
}
```
一起努力，如果觉得有用，请为我点个评分:innocent:~

0.0分

7 人评分

本文分类：题解列表
浏览次数：1167 次浏览
发布日期：2020-02-06 15:20:09
本文链接：https://blog.dotcpp.com/a/65542

上一篇 > 蓝桥杯算法提高VIP-输出正反三角形（Python代码）格式易错！！
下一篇 > A+B for Input-Output Practice (IV)-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 8 条评论

自由无畏 2年前回复TA

@东星耀阳 偏移的顺序是 D L R U

綮世 3年前回复TA

该死的学霸呜呜

东星耀阳 3年前回复TA

请问字母序怎么处理的

JakeLin 5年前回复TA

@纯洁的宇仔 @pureayu sorry~这代码贴这乱成一片了

纯洁的宇仔 5年前回复TA

@纯洁的宇仔 请问我这段代码为啥拼接不了，能输出数字，但字符串拼接不成

纯洁的宇仔 5年前回复TA

@纯洁的宇仔 #include <iostream>  #include <queue> #include <cstring> #include <string>  using namespace std; char maze[505][505]; bool vis[505][505]; struct node{  int x, y, d;  string s;  node(int xx, int yy, int dd){   x = xx;   y = yy;   d = dd;  } }; string d[4] = {"D","L","R","U"}; int dir[4][2] = {{1,0},{0,-1},{0,1},{-1,0}}; int n, m; int bfs(int x, int y){  queue<node> s;  s.push(node(x, y, 0));  vis[x][y] = true;  while(!s.empty()){   node now = s.front();   s.pop();   if(now.x == n && now.y == m){    cout << now.d << endl << now.s << endl;    return true;   }   for(int i = 0; i < 4; i ++){    int tx = now.x + dir[i][0];    int ty = now.y + dir[i][1];    if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && !vis[tx][ty] && maze[tx][ty] != &#039;1&#039;){     now.s += d[i];     s.push(node(tx, ty, now.d + 1));     vis[tx][ty] = true;    }   }  } } int main(){  cin >> n >> m;  for(int i = 1; i <= n; i ++){   for(int j = 1; j <= m; j ++){    cin >> maze[i][j];   }  }   bfs(1, 1);  return 0; }

JakeLin 5年前回复TA

@纯洁的宇仔 谢谢~加油！

纯洁的宇仔 5年前回复TA

赞！

JakeLin-题解1923：蓝桥杯算法提高VIP-学霸的迷宫 （C++代码）

字符串连接

人口增长问题题解

乘方计算题解

3031：分解因数

评论列表 共有 8 条评论

发表评论 取消回复

JakeLin-题解1923：蓝桥杯算法提高VIP-学霸的迷宫（C++代码）

评论列表共有 8 条评论

发表评论取消回复