逃离迷宫 HDU 1728

2024-03-09 05:58
文章标签 hdu 迷宫 逃离 1728

本文主要是介绍逃离迷宫 HDU 1728,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem Description

  给定一个m × n (m行, n列)的迷宫,迷宫中有两个位置,gloria想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria可以穿越,有些地方是障碍,她必须绕行,从迷宫的一个位置,只能走到与它相邻的4个位置中,当然在行走过程中,gloria不能走到迷宫外面去。令人头痛的是,gloria是个没什么方向感的人,因此,她在行走过程中,不能转太多弯了,否则她会晕倒的。我们假定给定的两个位置都是空地,初始时,gloria所面向的方向未定,她可以选择4个方向的任何一个出发,而不算成一次转弯。gloria能从一个位置走到另外一个位置吗?

 

 

Input

  第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数,接下来为t组测试数据,每组测试数据中,
  第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数,接下来m行,每行包括n个字符,其中字符'.'表示该位置为空地,字符'*'表示该位置为障碍,输入数据中只有这两种字符,每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能转的弯数,(x1, y1), (x2, y2)表示两个位置,其中x1,x2对应列,y1, y2对应行。

 

 

Output

  每组测试数据对应为一行,若gloria能从一个位置走到另外一个位置,输出“yes”,否则输出“no”。

 

 

Sample Input

 

2

5 5

...**

*.**.

.....

.....

*....

1  1  1  1  3

5   5

...**

*.**.

.....

.....

*....

2  1  1  1  3

 

 

Sample Output

 

no

yes

 // 回溯 :因为 一个点只走一次 // 剪枝是这个题的精华: 需要设一个 turn[x][y] 来保存 经过x,y点得最小转弯次数。// 细节部分看代码 #include<stdio.h>#include<string.h>char map[110][110];int  turn[110][110];int n,m,k,flag,x2,y2;int dx[4] = { 1,-1,0,0};int dy[4] = { 0, 0,1,-1};int abs ( int a){if( a < 0)return  -a;return  a; }void dfs(int x ,int y ,int dir ){if( flag ==1)    //找到一个,就都返回。return ; int xx,yy;if(x==x2 && y==y2 && turn[x][y]  <=k){  flag = 1;           //正常结束条件 return ;}if(turn[x][y] > k)     // 不符合条件,剪去 return ;for(int i=0;i<4;i++){xx = x + dx[i];yy = y + dy[i];if( xx >=1 && yy >=1 && xx<=m && yy<=n && map[xx][yy] == '.'  ){map[xx][yy] = '*';if( dir ==-2 ){ turn[xx][yy] = 0;dfs(xx,yy,abs(dx[i]));}else if( dir != abs(dx[i]) ){if( turn[xx][yy] >= turn[x][y] +1){     		  	  	                       //判断条件://  一定是 turn[xx][yy] >= turn[x][y] +1 否则遗漏情况turn[xx][yy] = turn[x][y]+1;dfs( xx,yy,abs(dx[i]));		   }}else if(  dir == abs(dx[i]) ){if( turn[xx][yy] >= turn[x][y]){ turn[xx][yy] = turn[x][y];dfs( xx,yy,abs(dx[i]));}}	map[xx][yy] = '.';}    }	         }int main(void){int i,j,t,x1,y1;scanf("%d",&t);while(t--){scanf("%d%d",&m,&n);memset(turn,0x3f3f3f3f,sizeof(turn));for( i=1;i<=m;i++)for( j =1;j<=n;j++)scanf(" %c",&map[i][j]);scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);flag = 0;map[x1][y1] = '*';turn[x1][y1]= 0;dfs(x1,y1,-2);if(flag)printf("yes\n");else printf("no\n");}return 0;} 

 

这篇关于逃离迷宫 HDU 1728的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/789722

相关文章

上海邀请赛 A题目 HDU 5236(dp)

先求出没有ctrl+s的时候构造长度为i的期望f[i] 。然后枚举保存的次数,求出最小即可。 #include<cstdio>#include<cstdio>#include<cmath>#include<queue>#include<stack>#include<string>#include<cstring>#include<iostream>#include<map>

hdu 2586 树上点对最近距离 (lca)

,只要知道dis[i][j]=dis[i][root]+dis[j][root]-2*dis[Lca(i,j)][root].   其中root为树的根节点,LCA(i,j)为i,j的最近公共祖先。 所以我们先把所有的询问储存下来,然后离线直接查询。复杂度是o(n+q)的。 VIE #include<cstdio>#include<algorithm>#include<i

HDU_1013

这个题目尤其需要注意的是开始输入的时候的数的大小,开始输入时有可能非常的大超过了长整型的范围,所以不能开始用整形来存放输入的,,就是开始的时候没有注意到这个问题所以开始的时候一直没有AC,后来就是用一个数组接收输入,然后在经过第一步转化之后就可以用一个整数来装了 #include <iostream>#include <stdlib.h>#include <string>usin

最长回文子串(百度笔试题和hdu 3068)

版权所有。所有权利保留。 欢迎转载,转载时请注明出处: http://blog.csdn.net/xiaofei_it/article/details/17123559 求一个字符串的最长回文子串。注意子串是连续的,子序列是不连续的。对于最长回文子序列,要用动态规划解,具体请看: http://blog.csdn.net/xiaofei_it/article/details/1

杭电ACM hdu 2110 Crisis of HDU 解题报告(母函数)

Problem Description 话说上回讲到HDU大战东洋小苟,结果自然是中方大胜,这一战也使得海东集团在全球同行业中的地位更加巩固。随着集团的发展,很多创业时期的元老逐步功成身退,先是8600移民海外,然后是linle夫妇退隐山林,逐渐的,最初众多的元老只剩下XHD夫妇和Wiskey三人了。 到了2020年,因为扩张过度加上老鼠数量逐年减少,公司的发展遇到了前所未有的危机,此时集团已经

杭电ACM hdu 2082 找单词 解题报告(母函数)

Problem Description 假设有x1个字母A, x2个字母B,..... x26个字母Z,同时假设字母A的价值为1,字母B的价值为2,..... 字母Z的价值为26。那么,对于给定的字母,可以找到多少价值<=50的单词呢?单词的价值就是组成一个单词的所有字母的价值之和,比如,单词ACM的价值是1+3+14=18,单词HDU的价值是8+4+21=33。(组成的单词与排列顺序无关,比如

杭电ACM hdu 2079 选课时间 解题报告(母函数)

Problem Description 又到了选课的时间了,xhd看着选课表发呆,为了想让下一学期好过点,他想知道学n个学分共有多少组合。你来帮帮他吧。(xhd认为一样学分的课没区别)   Input 输入数据的第一行是一个数据T,表示有T组数据。 每组数据的第一行是两个整数n(1 <= n <= 40),k(1 <= k <= 8)。 接着有k行,每行有两个整数a(1 <= a <= 8),b

BFS【2】迷宫

目录 迷宫 走到右下角最短路径长度 走到右下角最短路径 跨步迷宫   迷宫 走到右下角最短路径长度 我是和上一篇一样,创建一个队列,不过while 里面判责是queue非空,否则会死循环万一是死路的话。 也是要判断不要重复入队。 #include <iostream>#include <vector>#include <cmath>#include <string>

洛谷 P1141 01迷宫 (dfs解决)

题目描述 有一个仅由数字 0 与 1 组成的 n×n 格迷宫。若你位于一格 0 上,那么你可以移动到相邻 4 格中的某一格 1 上,同样若你位于一格 1 上,那么你可以移动到相邻 4 格中的某一格 0 上。 你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。 输入格式 第一行为两个正整数 𝑛,𝑚。 下面 𝑛 行,每行 𝑛 个字符,字符只可能是 0 或者

逃离北京回家创业--生存篇

创业的路上,并不总是激情和乐趣。当激情过了,就需要面对赤裸裸的现实。 首先要考虑团队的开销问题,虽然大家拿的工资并不高,但是四个人的工资加上房租水电,对于一个穷苦出身的程序员来说也是个不小的压力。为了给团队找个能够发展下去的持续动力,我想了挺多的办法。 我们在大学城里面创业,大学生是很好的资源。我首先想到的是办培训,我反复思考,我觉得想到了一个非常理想的运作模式。我们创业缺少的是两