码是真不

用户名：leewentao

访问量：1795

签　名：

等　　级
排　　名	9029
经　　验	1186
参赛次数	0
文章发表	7
年　　龄	0
在职情况	学生
学　　校	xp
专　　业

　　自我简介：

TA的其他文章

问题 1936: 蓝桥杯算法提高VIP-最大乘积
浏览：110

蓝桥杯算法训练VIP-幂方分解-题解(C++代码)
浏览：267

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

蓝桥杯算法提高VIP-学霸的迷宫-题解(C++代码)

　　作者: 码是真不　　　　发表时间：2020-02-16 10:46:59 浏览：209　|　评论：0　

原题链接：蓝桥杯算法提高VIP-学霸的迷宫

**本题是求解最短路问题，所以不应该使用dfs，而是bfs，搜到最短路后返回，每一个坐标封装在一个结构体中，结构体有横坐标，纵坐标，步数和方向字符。注意：要将字符封装在每一个坐标中，因为bfs是寻找每一个符合要求的坐标，并插入队中，必然会插入不是最短路的字符，通过将字符存入结构体，记录每一个坐标的从起点到该点坐标的方向。题中讲到不同方向有相同最短路时选择序列小的，即D<L<R<U，故遍历顺序按此顺序判断。
```cpp
#include<iostream>
#include<queue>
#include<string>
using namespace std;
char array[510][510]={0};//存放字符的邻接矩阵
int vis[510][510]={0};//标记
int n,m;
struct node{
	int x;//行
	int y;//列
	int s;//step
	string val="";//方向初始化为空
	node(int xx,int yy,int ss){//只能存入整型
		x=xx;
		y=yy;
		s=ss;
	}
};
int b1[4]={1,0,0,-1};//DLRU
int b2[4]={0,-1,1,0};
void bfs()
{
	queue<node> q;
	q.push(node(0,0,0));
	while(!q.empty()){
		node X=q.front();
		q.pop();
		if(X.x==n-1&&X.y==m-1){
			cout<<X.s<<endl;
			cout<<X.val<<endl;
		}
		for(int i=0;i<4;i++){
			int a=X.x+b1[i];
			int b=X.y+b2[i];
			int step=X.s;
			string c=X.val;
			if(!vis[a][b]&&array[a][b]=='0'&&a>=0&&a<n&&b>=0&&b<m){
				vis[a][b]=1;
				node Y=node(a,b,step+1);//定义一个结构体
				switch(i){
					case 0:Y.val=c+'D';break;
					case 1:Y.val=c+'L';break;
					case 2:Y.val=c+'R';break;
					case 3:Y.val=c+'U';break;
				}//改变Y.val的值
				q.push(Y);
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++){
		cin>>array[i][j];
	}
	vis[0][0]=1;
	bfs();
	system("pause");
	return 0;
}

```

0.0分

0 人评分

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

码是真不

TA的其他文章

你可能喜欢

汽水瓶（C语言代码）

开心的金明（C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

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

C二级辅导-进制转换（C语言代码）

蓝桥杯算法提高VIP-学霸的迷宫-题解(C++代码)

评论区

精彩推荐

哥德巴赫曾猜测（C语言代码）

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

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

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

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

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

1113题解

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

矩形面积交（C语言代码）

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

码是真不

TA的其他文章

你可能喜欢

汽水瓶 （C语言代码）

开心的金明 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

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

C二级辅导-进制转换 （C语言代码）

蓝桥杯算法提高VIP-学霸的迷宫-题解(C++代码)

评论区

精彩推荐

哥德巴赫曾猜测 （C语言代码）

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

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

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

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

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

1113题解

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

矩形面积交 （C语言代码）

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

汽水瓶（C语言代码）

开心的金明（C++代码）

C二级辅导-进制转换（C语言代码）

　　评论区

哥德巴赫曾猜测（C语言代码）

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

矩形面积交（C语言代码）