帅气的HYC迷路了
作者：喂╲偶稀飯妳 | 来源：互联网 | 2023-05-18 18:50
描述有一天,我们帅气的HYC找到了一张藏宝图,这张图很神奇,只要你看它一眼,立马就会被传送到一个迷宫里,这个迷宫仅有一个出口.那么现在问题来啦,问你找到这个出口需要走多少步
有一天, 我们帅气的HYC找到了一张藏宝图, 这张图很神奇, 只要你看它一眼, 立马就会被传送到一个迷宫里, 这个迷宫仅有一个出口.那么现在问题来啦, 问你找到这个出口需要走多少步?
现在给出HYC在迷宫房中走的规则, HYC每走出一步, 都会优先向左走, 如果左边是墙, 那么他会向前走, 如果前边也是墙, 那么他就会向右走, 如果右边也是墙, 那么他只能选择后退了~~~~>_<~~~~
另外, HYC也想知道如果不这样走, 他最少能走多少步能走出出口呢?
首先给出一个T (1 <= T <100) 代表T组测试数据 每组测试数据第一行为两个整数r 和 c (3 <= r,c <= 40) r代表这个迷宫有多少列,c代表这个迷宫有多少行. S表示入口, E表示出口, #表示墙不能走, .表示空白区域, 可以走. 题目保证给出的迷宫四周都是墙, 而且按照规则走总能找到出口, 且初始方向为向北走,快来帮帮他吧!
每组数据输出两个数, 第一个数表示按照规则走的步数, 第二个数表示走到出口最短需要多少步.
复制1
9 5
#########
#.#.#.#.#
S.......E
#.#.#.#.#
#########
17 9
好受伤又好激动，一个月了，终于自己独立的写好了一个搜索【泪奔】
- #include
- #include
- #include
- //左前右后
- int n, m, p, q;
- char a[45][45];
- int book[45][45];
- int judge(int x,int y) {
- return (x >= 0 && x = 0 && y
- }
- int dfs(int x, int y, int dir, int step) {
- //dir 0:左 1上 2右 3后
- // x-1,y
- // x,y-1 x,y x,y+1
- // x+1,y
- int tx, ty;
- int next[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
- for(int k = 0; k <4; k++) {
- if(x == p && y == q) return (step + 1);
- int ndir = (dir + k + 3) % 4;
- tx = x + next[ndir][0];
- ty = y + next[ndir][1];
- if(!judge(tx,ty)) continue;
- return dfs(tx,ty,ndir,step+1);
- }
- }
- struct node {
- int x;
- int y;
- int dir;
- int step;
- }que[2500];
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--) {
- memset(a,0,sizeof(a));
- int startx, starty;
- scanf("%d%d",&m,&n);
- for(int i = 0; i
- getchar();
- for(int j = 0; j
- a[i][j] = getchar();
- if(a[i][j] == 'S') {
- startx = i;
- starty = j;
- }
- if(a[i][j] == 'E') {
- p = i;
- q = j;
- }
- }
- }
- int step = dfs(startx,starty,1,0);
- printf("%d ",step);
- /****************hualidefengexian*****************/
- memset(que,0,sizeof(que));
- memset(book,0,sizeof(book));
- int head, tail;
- head = tail = 1;
- book[startx][starty] = 1;
- que[tail].x = startx;
- que[tail].y = starty;
- que[tail].dir = 0;
- que[tail].step = 0;
- tail++;
- int flag = 0;
- int next[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
- while(head
- for(int k = 0; k <4; k++) {
- int ndir = (que[head].dir + k + 3) % 4;
- int tx = que[head].x + next[ndir][0];
- int ty = que[head].y + next[ndir][1];
- if(judge(tx,ty) && book[tx][ty] == 0) {
- book[tx][ty] = 1;
- que[tail].x = tx;
- que[tail].y = ty;
- que[tail].dir = ndir;
- que[tail].step = que[head].step + 1;
- tail++;
- }
- if(tx == p && ty == q) {
- flag = 1;
- break;
- }
- }
- if(flag == 1) break;
- head++;
- }
- printf("%d\n",que[tail-1].step + 1);
- }
- return 0;
- }
推荐阅读
-
golang常用库：配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库，是由大神SteveFrancia开发，他在google领导着golang的 ...
[详细]
蜡笔小新 2024-12-28 13:47:52
-
本文详细介绍了IBM DB2数据库在大型应用系统中的应用，强调其卓越的可扩展性和多环境支持能力。文章深入分析了DB2在数据利用性、完整性、安全性和恢复性方面的优势，并提供了优化建议以提升其在不同规模应用程序中的表现。 ...
[详细]
蜡笔小新 2024-12-28 13:22:19
-
-
本文详细介绍了HTML中标签的使用方法和作用。通过具体示例，解释了如何利用标签为网页中的缩写和简称提供完整解释，并探讨了其在提高可读性和搜索引擎优化方面的优势。 ...
[详细]
蜡笔小新 2024-12-27 17:05:37
-
本文介绍了如何在最新版本的Visual Studio Code中配置中文语言包，使用户能够更便捷地使用中文界面。文章详细描述了安装和配置步骤，并提供了相关补充说明。 ...
[详细]
蜡笔小新 2024-12-27 17:00:20
-
在哈佛大学商学院举行的Cyberposium大会上，专家们深入探讨了开源软件的崛起及其对企业市场的影响。会议指出，开源软件不仅为企业提供了新的增长机会，还促进了软件质量的提升和创新。 ...
[详细]
蜡笔小新 2024-12-27 14:49:56
-
新冠肺炎疫情期间，各大银行积极利用手机银行平台，满足客户在金融与生活多方面的需求。线上服务不仅激活了防疫相关的民生场景，还推动了银行通过互联网思维进行获客、引流与经营。本文探讨了银行在找房、买菜、打卡、教育等领域的创新举措。 ...
[详细]
蜡笔小新 2024-12-27 14:15:52
-
本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ...
[详细]
蜡笔小新 2024-12-27 13:55:14
-
本文详细介绍了360SRC平台处理一起关键安全事件的过程，涵盖从漏洞提交、验证、排查到最终修复的各个环节。通过这一案例，展示了360在安全应急响应方面的专业能力和严谨态度。 ...
[详细]
蜡笔小新 2024-12-27 11:10:05
-
本章将深入探讨移动 UI 设计的核心原则，帮助开发者构建简洁、高效且用户友好的界面。通过学习设计规则和用户体验优化技巧，您将能够创建出既美观又实用的移动应用。 ...
[详细]
蜡笔小新 2024-12-27 08:43:40
-
本文介绍如何在PHPCMS V9中创建和管理多个站点，包括配置独立域名、设置动态URL，并确保各子站能够正常运行。我们将详细讲解从新建站点到最终配置路由的每一步骤。 ...
[详细]
蜡笔小新 2024-12-27 05:15:58
-
本文详细解析了Python中的os和sys模块，介绍了它们的功能、常用方法及其在实际编程中的应用。 ...
[详细]
蜡笔小新 2024-12-26 22:04:19
-
在项目开发中，有时会遇到电脑只能连接内网或完全无法联网的情况。本文将详细介绍如何在这种环境下安装Python及其所需的第三方库，确保开发工作的顺利进行。 ...
[详细]
蜡笔小新 2024-12-26 19:51:48
-
本文将详细介绍如何利用Python的Paramiko库实现远程执行Linux脚本和命令，帮助读者快速掌握这一实用技能。通过具体的示例和详尽的解释，让初学者也能轻松上手。 ...
[详细]
蜡笔小新 2024-12-26 19:47:05
-
本文将详细介绍在Windows 7环境下，检查U盘启动盘是否制作成功的多种方法，包括通过BIOS设置和使用模拟启动工具。 ...
[详细]
蜡笔小新 2024-12-26 19:40:06
-
本文详细探讨了 H5C3 和 JavaScript 中的一些核心编程问题，通过实例解析和代码示例，帮助开发者更好地理解和应用这些技术。 ...
[详细]
蜡笔小新 2024-12-26 18:28:05
-
京公网安备 11010802041100号