程序员经验分享-hwhale

2019年第十届蓝桥杯省赛A组（C/C++组）迷宫（BFS）

2023-10-31

试题 D: 迷宫
【问题描述】
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。

010000
000100
001001
110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。
对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务 必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt， 内容与下面的文本相同）

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

答案：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

思路：
（1）首先01地图中找最短路，肯定选择广度优先级搜索（BFS）。

（2）然后需要路径，只需要在搜索过程中记录下每个节点由什么操作转换（或者记录前一个节点的二维坐标），之后再反向沿着路径找回去就知道了走法。

（3）最后还需要字典序最小，那么我们可以考虑方向数组的4个方向向量的顺序。想到的方法是，从右下角节点 T(n,m) 开始，向左上角S(1,1) 搜索找路径。同时维护好每个坐标点是如何由上一坐标点到达。

（4）由于字典序最小，那我们安排优先走字典序小的方向，每次都走最小的，那最后结果也是最小的。

（5）由于bfs是记录上一步的坐标位置，所以我们从右下角向左上角来走，每次走最大的，那从左上角到右上角便是最小的啦。

按这样便可以输出路径了！！

这道题确实坑...

(最标准的答案代码在最后）

打印移动步骤
#include<iostream>
#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
struct box
{
	int x, y;
};
class queue//可以不用定义类，我练习一下
{
public:
	queue() { T = new box[400]; front = 0; rear = 0; }
	void push(box x)
	{
		T[rear] = x;
		rear++;
		
	}
	void pop()
	{
		front++;

		
	}
	bool isempty()
	{
		if (front  == rear)
			return true;
		else false;
	}
	box getfront()
	{
		return T[front];
	}
	box *T;
	int front;
	int rear;
};
int main()
{
	queue qu;//如果不定义的话，换成queue<box> qu;
	box q;
	int path[20][20];
	char maze[20][20];
	bool visit[20][20];
	int output[400][2];//用于输出路径
	memset(visit, false, sizeof(visit));
	int m, n;
	int x0, y0;//记录起点的位置
	int di[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };//上下左右四个方向

	char S[4] = { 'U','D','L','R' };
	bool flag;
	cout << "输入迷宫的行数和列数" << endl;
	
	cin >> m >> n;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> maze[i][j];
			if (maze[i][j] == 'E')
			{
				x0 = i, y0 = j;

			}

		}
	}
	//起点进队列
	q.x = x0; q.y = y0;
	qu.push(q);
	visit[q.x][q.y] = true;//已经访问过了
	//开始搜索
	flag = false;
	while (qu.isempty() != true && flag ==false)
	{
		box temp = qu.getfront();
		qu.pop();
		for (int i = 0; i < 4; i++)
		{
			q.x = temp.x + di[i][0];
			q.y = temp.y + di[i][1];
			if (q.x < 0 || q.x >= m || q.y < 0 || q.y >= n)
			{
				continue;
			}
			if (maze[q.x][q.y] != '*'&&visit[q.x][q.y] ==false)//该点能走

			{
				qu.push(q);
				path[q.x][q.y] = i;
				if (maze[q.x][q.y] == 'S')//找到目标
				{
					flag = true;
					break;
				}
				visit[q.x][q.y] = true;
			}
		}
		

	}//搜索结束
	if (flag == true)
	{
		int step = 0;
		while (q.x != x0 || q.y != y0)
		{
			switch (path[q.x][q.y])
			{
			case 0:
				cout << "D";
				q.x = q.x + 1;
				break;
			case 1:
				cout << "U";
				q.x = q.x - 1;
				break;

			case 2:
				cout << "R";
				q.y = q.y + 1;
				break;

			case 3:
				cout << "L";
				q.y = q.y - 1;
				break;
			}
			/*output[step][0] = q.x;
			output[step][1] = q.y;
			int x = q.x;
			q.x = path[q.x][q.y].x;
			q.y = path[x][q.y].y;
			step++;*/
		}
		/*cout << "输出路径为：" << endl;
		for (int i = step - 1; i >= 0; --i)
		{
			cout << "(" << output[i][0] << "," << output[i][1] << ")" << endl;
		}*/
	}
	else
		cout << "迷宫无解" << endl;

	system("pause");
	return 0;
}

相似的迷宫题目

就是上面这道题的基础版本，有利于理解上面一题

Sample Input

15 16

.**.***.***.***

***.***..**.*.*

.**.***.***.***

***.***..**.*.*

**.***.***.***.

***.***.......E

.**.***.***.*.*

***..**...*...*

.*....*.*...*.*

***.*.*.**.*..*

....*...**...**

*.*.***..**.*.*

.S*.***.***.***

***.***..**.*.*

.**.***.***.**.

***..**...*...*

Sample Output

The path is:

(11,1) (10,1) (10,2) (10,3) (9,3) (8,3) (8,4) (8,5) (9,5) (10,5) (10,6) (10,7) (9,7) (8,7) (7,7) (6,7) (5,7) (5,8) (5,9) (5,10) (5,11) (5,12) (5,13) (5,14)

首先输入两个数代表迷宫的行数和列数,‘.’代表可以走的点，'*'代表墙，即不可以走的点。‘S’代表迷宫的入口，‘E’代表迷宫的出口。

由于广搜中，队列中的每一点被搜索到时都是在离起点最短的路径中被搜索到的，所以可以再建立一个以点的坐标为数据元素的二维数组，该二维数组每个数据元素对应迷宫中的每个点，其数据元素的值为该点在离起点最短的路径中的前一个点的坐标。这样迷宫的路径便不再由队列元素保存，所以出队并不影响路径的输出。

思路类似：本质都是利用bfs记录上一步的元素，然后输出

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
struct box
{
	int x, y;
};
class queue
{
public:
	queue() { T = new box[400]; front = 0; rear = 0; }
	void push(box x)
	{
		T[rear] = x;
		rear++;
		
	}
	void pop()
	{
		front++;

		
	}
	bool isempty()
	{
		if (front  == rear)
			return true;
		else false;
	}
	box getfront()
	{
		return T[front];
	}
	box *T;
	int front;
	int rear;
};
int main()
{
	queue qu;
	box q;
	box path[20][20];
	char maze[20][20];
	bool visit[20][20];
	int output[400][2];//用于输出路径
	memset(visit, false, sizeof(visit));
	int m, n;
	int x0, y0;//记录起点的位置
	int di[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };//上下左右四个方向
	bool flag;
	cout << "输入迷宫的行数和列数" << endl;
	
	cin >> m >> n;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> maze[i][j];
			if (maze[i][j] == 'S')
			{
				x0 = i, y0 = j;

			}

		}
	}
	//起点进队列
	q.x = x0; q.y = y0;
	qu.push(q);
	visit[q.x][q.y] = true;//已经访问过了
	//开始搜索
	flag = false;
	while (qu.isempty() != true && flag ==false)
	{
		for (int i = 0; i < 4; i++)
		{
			q.x = qu.getfront().x + di[i][0];
			q.y = qu.getfront().y + di[i][1];
			if (q.x < 0 || q.x >= m || q.y < 0 || q.y >= n)
			{
				continue;
			}
			if (maze[q.x][q.y] != '*'&&visit[q.x][q.y] ==false)//该点能走

			{
				qu.push(q);
				path[q.x][q.y] = qu.getfront();
				if (maze[q.x][q.y] == 'E')//找到目标
				{
					flag = true;
					break;
				}
				visit[q.x][q.y] = true;
			}
		}
		qu.pop();

	}//搜索结束
	if (flag == true)
	{
		int step = 0;
		while (q.x != x0 || q.y != y0)
		{
			output[step][0] = q.x;
			output[step][1] = q.y;
			int x = q.x;
			q.x = path[q.x][q.y].x;
			q.y = path[x][q.y].y;
			step++;
		}
		cout << "输出路径为：" << endl;
		for (int i = step - 1; i >= 0; --i)
		{
			cout << "(" << output[i][0] << "," << output[i][1] << ")" << endl;
		}
	}
	else
		cout << "迷宫无解" << endl;

	system("pause");
	return 0;
}

简易版本 

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<string.h>
using namespace std;
struct box
{
	int x, y;
	box(int a, int b)
	{
		x = a;
		y = b;


	}
	box() {};
};
queue<box> qu;
box q;
box path[20][20];
char maze[20][20];
bool visit[20][20] = {0};
int output[400][2];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };

int main()
{
	int x0, y0;
	int m, n;
	cin >> m >> n;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> maze[i][j];
			if (maze[i][j] == 'S')
			{
				x0 = i;
				y0 = j;
			}
		}
	}

	bool flag = false;

	queue<box> qu;
	box q(x0, y0);
	qu.push(q);
	visit[x0][y0] = 1;
	int dx, dy;
	while (!qu.empty()&&flag==false)
	{
		box t = qu.front();
		qu.pop();
		
		
		for (int i = 0; i < 4; i++)
		{
			dx = t.x + dir[i][0];
			dy = t.y + dir[i][1];
			if (dx < m&&dy < n&&dx >= 0 && dy >= 0)
			{
				if (maze[dx][dy] != '*'&&visit[dx][dy] == 0)
				{
					box qt(dx, dy);
					path[dx][dy] = t;
					

					qu.push(qt);
					visit[dx][dy] = 1;
					if (maze[dx][dy] == 'E')
					{
						flag = true;
						break;
					}
					
				}
			}
		}
	}

	box t;
	int step = 0;
	int x1;
	
	while (dx!= x0 || dy != y0)
	{
		output[step][0] = dx;
		output[step][1] = dy;
		x1 = dx;
		dx=path[dx][dy].x;
		dy = path[x1][dy].y;

		step++;
		


	}
	for (int i = step - 1; i >= 0; i--)
	{
		cout << "(" << output[i][0] << "," << output[i][1] << ")" << endl;
	}
	system("pause");
	return 0;
}

补充：！！！

确实可以记录上一步的步骤，但我们可以走到某个点，就把这个点的路径设为之前的路径加上走到这一步的路径，最后在直接输出最后一个点的记录的所有路径。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<set>
using namespace std;
 
#define N 30
#define M 50
 
char map[N][M];
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};//D<L<R<U
char ch[4]={'D','L','R','U'};
int vis[N][M]={0};
 
struct point
{
	int x,y;
	string road;//记录路径到这一个点的路径
	point(int a,int b)
	{
		x=a;
		y=b;
	}
};
 
void bfs()
{
	queue<point> q;
	point p(0,0);
	p.road="";
	q.push(p);
	vis[0][0]=1;
	while(!q.empty())
	{
		point t=q.front();
		q.pop();
		if(t.x==N-1&&t.y==M-1)
		{
			cout<<t.road<<endl;//输出
			break;
		}
		for(int i=0;i<4;i++)
		{
			int dx=t.x+dir[i][0];
			int dy=t.y+dir[i][1];
			if(dx>=0&&dx<N&&dy>=0&&dy<M)
			{
				if(map[dx][dy]=='0'&&!vis[dx][dy])
				{
					point tt(dx,dy);
					tt.road=t.road+ch[i];//记录路径
					q.push(tt);
					vis[dx][dy]=1;
				}
			}
		}
	}
}
 
int main()
{
	for(int i=0;i<N;i++)
	{
		cin>>map[i];
	}
	bfs();
	return 0;
}

 

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

蓝桥杯

BFS

2019年第十届蓝桥杯省赛A组（C/C++组）迷宫（BFS） 的相关文章

  • 第六题 整除排序

    题目描述 有一个序列 序列的第一个数是n 后面的每个数是前一个数整除2 请输出这个序列中的值为正数 的项 输入格式 输入一行包括一个整数n 输出格式 输出一行 包括多个整数 相邻的整数之间用一个空格分开 表示答案 测评用例规模和标准 对于8

  • Acwing2554. 排列数

    在一个排列中 一个折点是指排列中的一个元素 它同时小于两边的元素 或者同时大于两边的元素 对于一个 1 n 的排列 如果可以将这个排列中包含 t 个折点 则它称为一个 t 1 单调序列 例如 排列 1 4 2 3 是一个 3 单调序列 其中

  • 一种关于单片机定时器中断和数码管冲突问题的解决方案

    问题发现 我们会发现 同时存在定时器中断和数码管操作时 有时会导致数码管显示异常 原因探究 在定时器中断函数中不要操作P2和P0 因为定时器 T 和主板 M 的时钟频率不一样 有可能导致M刚操作完P2 T又去操作P0 导致正确的P2和P0没

  • Acwing 842. 排列数字

    dfs int u 搜索第u个位置上可以放哪个数字 include

  • 蓝桥杯 辗转相除法---求最大公约数

    1 例子 例如 求 319 377 319 377 0 余319 319 377 377 319 377 319 1 余58 377 319 319 58 319 58 5 余29 319 58 58 29 58 29 2 余0 58 29

  • 备战2023蓝桥国赛-传纸条

    题目描述 解析 这道题想了我好久 一开始我是想假如只走一条路线 从 1 1 走到 m n 这种问题该怎么解决呢 针对这种问题我是设了dp k i j 表示走了k步到达 i j 的好心程度之和的最大值 然后根据这个来写出转移方程来计算 后面就

  • 洛谷-【入门4】数组

    1 小鱼比可爱 题目描述 人比人 气死人 鱼比鱼 难死鱼 小鱼最近参加了一个 比可爱 比赛 比的是每只鱼的可爱程度 参赛的鱼被从左到右排成一排 头都朝向左边 然后每只鱼会得到一个整数数值 表示这只鱼的可爱程度 很显然整数越大 表示这只鱼越可

  • 备战2023蓝桥国赛-饼干

    题目描述 解析 这道题我想了很多种解决方法 但无一例外都失败了 实在是按照常规线性DP的思路真的想不出来 看了题解之后才知道它是分为三步解决这个问题的 第一步 缩小最优解的范围 先用贪心将最优解缩小到某个较小的范围内 再DP求出精确的最优解

  • openGL之API学习（一九三）glGenTextures

    生成纹理单元名 单元名不一定是连续的 但是没有使用的 单元名是相对GL TEXTURE0的 对于单元名1 其实是GL TEXTURE0 1 glGenTextures产生的是一个比较小的整数id 纹理单元名 glActiveTexture激

  • 蓝桥杯.卡片(模拟)

    Question Result 3181 Solve 直接模拟暴力 初始化卡片数量为2021 去模拟拼数的过程 注意点的话 我是先去判断卡片还有没有 再去减一 所以输出结果也有一个减一 因为一旦说卡片没有了 就意味着当前这个数字拼不成了 C

  • 蓝桥杯最长不下降子序列，线段树python

    问题描述 给定一个长度为 N 的整数序列 A1 A2 AN 现在你有一次机会 将其 中连续的K 个数修改成任意一个相同值 请你计算如何修改可以使修改后的数 列的最长不下降子序列最长 请输出这个最长的长度 最长不下降子序列是指序列中的一个子序

  • 树与二叉树（二叉树的表示，性质，遍历，还原）

    1 基本术语 A 或B 是I的祖先 I是A 或B 的子孙 D是I的双亲 I是D的孩子 节点的孩子个数称为节点的度 树中节点的最大度数称为树的度 度大于0的节点称为分支节点 度等于0的节点称为叶节点 定义树根为第一层 则 树的深度 高度 为5

  • 蓝桥杯C/C++百校真题赛（3期）Day3(考勤刷卡、最大和)

    Day3 Q1 考勤刷卡 Q2 最大和 Q1 考勤刷卡 问题描述 小蓝负责一个公司的考勤系统 他每天都需要根据员工刷卡的情况来确定 每个员工是否到岗 当员工刷卡时 会在后台留下一条记录 包括刷卡的时间和员工编号 只 要在一天中员工刷过一次卡

  • 蓝桥杯每日一题2023.9.16

    蓝桥杯2022年第十三届省赛真题 X进制减法 C语言网 dotcpp com 题目描述 进制规定了数字在数位上逢几进一 X 进制是一种很神奇的进制 因为其每一数位的进制并不固定 例如说某种 X 进制数 最低数位为二进制 第二数位为十进制 第

  • Open Camera异常分析(一)

    负责的项目中遇到一些三方和其他的场景使用camera导致问题 并且没有及时释放camera device致使手机camera应用一直无法使用的严重问题 针对这类问题进行了一系列的分析与追踪 最后算是定位到了问题且提供了一些解决方案 但整个追

  • G - Ginger的NB数（二分）

    G Ginger的NB数 SDUT OnlineJudge include

  • 【快速选择算法】O(n)时间复杂度

    快速选择的期望时间复杂度为O n 最坏时间复杂度为O n 2 当每次划分只划分为n 1个和1个时 由于划分时间复杂度为O n 最坏时间复杂度为O n 2 void quickselect vector

  • 多少个X 蓝桥杯模拟

    问题描述 给定一个字母矩阵 一个 X 图形由中心点和由中心点向四个45度斜线方向引出的直线段组成 四条 线段的长度相同 而且四条线段上的字母和中心点的字母相同 一个 X图形可以使用三个整数 r c L 来描述 其中 r c 表示中心点位于第

  • 字符串处理-第11届蓝桥杯省赛Python真题精选

    导读 超平老师的Scratch蓝桥杯真题解读系列在推出之后 受到了广大老师和家长的好评 非常感谢各位的认可和厚爱 作为回馈 超平老师计划推出 Python 蓝桥杯真题解析100讲 这是解读系列的第26讲 字符串处理 本题是2020年6月20

  • 如何查看崩溃日志

    目录 描述 思路 查看ipa包崩溃日志 简单查看手机崩溃信息几种方式 方式1 手机设置查看崩溃日志 方式2 Xocde工具 方式3 第三方软件克魔助手 环境配置 实时日志 奔溃日志分析 方式四 控制台资源库 线上崩溃日志 线上监听crash

随机推荐

热门标签