蓝桥杯(迷宫问题)

这篇具有很好参考价值的文章主要介绍了蓝桥杯(迷宫问题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目:X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。
房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立,则:
L表示走到左边的房间,R表示走到右边的房间,U表示走到上坡方向的房间,D表示走到下坡方向的房间。
X星球的居民有点懒,不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此!
开始的时候,直升机把100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。
迷宫地图如下:
------------
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
---------------- 

 主要思想:dfs(深度优先搜索) 和递归。

个人思路:

1.先建议一个字符型二维数组place(10*10)来存放方向D,U,L,R;

2.遍历place的每个点,查询该点是否可以走出去。

注意:遍历每个点之前要先初始化FLAG,以防每个点之间的数据相互影响。

3.再建立一个整型二维数组FLAG(12*12),其作用有两个:

一个是为了标记走过的路径,二是为了检查是否走出迷宫。初始化的FLAG如图所示:

1代表已经出迷宫,0代表还在迷宫内 ,当走过一个点时,将0修改为INF。INF的意思已经走过的点。

蓝桥杯(迷宫问题)

4.如果已经走出迷宫直接返回1,如果已经进入循环则返回0,其他情况则根据当前迷宫格的情况继续行走。如果继续走的情况则先将该点的标志数组的值变为INF,然后递归DFS函数。

代码如下: 

#include<iostream>
using namespace std;
char place[12][12];
int FLAG[12][12];
const int INF = 2;
int peoplenum = 0;
bool dfs(int x, int y, char M) {
	//如果进入已经经过的点,就返回0
	if (FLAG[x][y] == INF)  return 0;
	//如果已经出迷宫就返回1
	else  if (FLAG[x][y] == 1)  return 1;
//可以继续走的情况
//nx,ny分别表示下一个点的行和列
	if (FLAG[x][y] == 0) {
		//U为向上走,y不变,x减少1
		if (M == 'U') {
           //将该点在标志数组中所对应的位置的值变为INF
			FLAG[x][y] = INF;
			int nx = x - 1;
			int ny = y;
			return  dfs(nx, ny, place[nx][ny]);
		}
//D为向下走,y不变,x加上1
		if (M == 'D') {
			FLAG[x][y] = INF;
			int	nx = x + 1;
			int 	ny = y;
			return  dfs(nx, ny, place[nx][ny]);

		}
//R为向右走,x不变,y加1
		if (M == 'R') {
			FLAG[x][y] = INF;
			int	nx = x;
			int	ny = y + 1;
			return  dfs(nx, ny, place[nx][ny]);
		}
		if (M == 'L')
//L为向左走,x不变,y-1
		{
			FLAG[x][y] = INF;
			int	nx = x;
			int	ny = y - 1;
			return  dfs(nx, ny, place[nx][ny]);
		}
	}
	return 0;

}
void chongzhi() {
	//标志数组先全定位0
	for (int i = 0; i <= 11; i++) {
		for (int j = 0; j <= 11; j++) {
			FLAG[i][j] = 0;
		}
	}
	//对第0和11列特殊赋值为1
	for (int i = 0; i <= 11; i++) {
		FLAG[i][0] = 1;
		FLAG[i][11] = 1;
	}
	//对第0行和11特殊赋值为1
	for (int i = 0; i <= 11; i++) {
		FLAG[0][i] = 1;
		FLAG[11][i] = 1;
	}
}
void solve() {
	for (int h = 1; h <= 10; h++)
		for (int l = 1; l <= 10; l++) {
			//查询新的迷宫格,重置标志数组
			chongzhi();
			//调用dfs函数,如果返回1则说明该迷宫格可以走出去,那么走出去的人数则加上1
			if (dfs(h, l, place[h][l])) peoplenum++;

		}
	cout << peoplenum;
}
int main() {
//输入迷宫的情况
	for (int i = 1; i <= 10; i++)
		for (int j = 1; j <= 10; j++) {
			cin >> place[i][j];
		}
	solve();
	return 0;
}

个人心得:

1.一开始犯错的点在U向上的写成-1,D向下写成+1。导致答案错误。

2.开一个标志数组个人认为比较方便一些,因为要检查是否已经经过的该迷宫点和迷宫边界比较难处理。

留言:还有一些不足和可以优化的地方,有建议可指教一下~文章来源地址https://www.toymoban.com/news/detail-414264.html

到了这里,关于蓝桥杯(迷宫问题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 迷宫 蓝桥杯

    问题描述 这天, 小明在玩迷宫游戏。 迷宫为一个 n×n 的网格图, 小明可以在格子中移动, 左上角为 (1,1), 右下角 (n, n)为终点。迷宫中除了可以向上下左右四个方向移动一格以外, 还有 m 个双向传送门可以使用, 传送门可以连接两个任意格子。 假如小明处在格子(x1​,y1​), 同

    2024年02月07日
    浏览(31)
  • 蓝桥杯(迷宫,C++)

     思路: 1、注意输入用字符串。 2、采用广度搜素的方法来求解。 3、因为最后要求字典序最小且DLRU,所以在遍历四个方向的时候, 先向下,再向左、右,最后向上。

    2024年02月07日
    浏览(37)
  • 迷宫(蓝桥杯C/C++)dfs详解

    题目描述 下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可以通行的地方。 110000迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫,从入口开始,可以按 DRRURRDDDR 的顺序通过

    2023年04月08日
    浏览(35)
  • 【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

    📖📖 走迷宫 一类的问题一般都是暴力搜索解决,搜索的方法有两种:深度优先(DFS)和广度优先(BFS),而提到DFS就离不开递归,涉及到递归的问题理解起来还是有难度的,代码编写不当很容易造成栈溢出。 🌻🌻今天就用三道 走迷宫 问题带你彻底搞懂怎么用DFS秒杀迷宫

    2023年04月11日
    浏览(39)
  • 蓝桥杯官网题目:2.包子凑数

    链接: 题目点这里 首先要知道一个数学定理裴蜀定理,还有完全背包的基本运用,这里只介绍前者 也可以看一下我的个人理解,我是第一次听说这个定理,理解可能有误差。 假设gcd(a,b)=d,gcd是最大公约数的意思。即a,b的最大公约数是d ax+by=m(x,y是任意整数,可正可负) 对

    2024年01月21日
    浏览(48)
  • 蓝桥杯宝藏排序题目算法(冒泡、选择、插入)

    从左往右找到最小的元素,放在起始位置;重复上述步骤,依次找到第2小、第3小元素... 第0次循环从[0,n-1]中找最小元素a[x],与a[0]交换 第1次循环从[1,n-1]中找最小元素,与a[1]交换 第2次循环从[2,n-1]中找最小元素,与a[2]交换 第i次循环从[i,n-1]中找最小元素,与a[i]交换 第n-2次循

    2024年01月17日
    浏览(38)
  • 蓝桥杯单片机第14届省赛客观题目+程序题目+程序题参考答案

    目录 客观题题目 程序题题目 程序题参考答案 main.h main.c Init.h Init.c SMG.h SMG.c DSQ.h DSQ.c YanShi.h YanShi.c JZKey.h JZKey.c ds1302.h ds1302.c iic.h iic.c onewire.h onewire.c LN555.h LN555.c             首先吐槽一下,花300元体验国赛的难度,是真的崩溃。          3个小时写完,2个小时改bug!

    2024年02月11日
    浏览(241)
  • 2019蓝桥杯省赛题目——“数的分解”

    目录 题目 要求 思路 最后的代码 结果 把 2019 分解成 3 个各不相同的正整数之和,并且要求每个正整数都不包含数字 2 和 4,一共有多少种不同的分解方法? 注意交换 3 个整数的顺序被视为同一种方法,例如 1000+1001+18 和 1001+1000+18 被视为同一种。 这是一道结果填空

    2024年02月14日
    浏览(40)
  • 蓝桥杯嵌入式第十届初赛题目解析

     最近写完了嵌入式第十届初赛的题目,拿出来和大家分享,希望帮助解决一些问题。 目录 客观题  程序设计题 题目解析 CubeMX配置  代码演示  收集的一些历年的比赛客观题和解析,以及程序设计题的PDF,在这里分享给大家。  链接 :https://pan.baidu.com/s/1hTw0inSbLjX57hOtankgKw 

    2023年04月11日
    浏览(49)
  • 蓝桥杯嵌入式第十四届省赛题目解析

    前几天刚刚参加完第十四届的省赛,这届题目比我想象中的要难,其实想一想这也是应该的,以前的知识点都被摸透了,也是需要加入新的知识点了,但是我还是想说能不能别在我参加的时候加大题目难度啊。 不过听说隔壁单片机的省赛都比往年的国赛还难,这就有点离谱了

    2024年02月06日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包