A计划
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13301 Accepted Submission(s):
3284
Problem Description
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S(0，0，0)，公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。
Input
输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M(1
<= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。
Output
如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。
Sample Input
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#..
Sample Output
YES
注意：1、如果两层的同一个位置都是#或者#对应另一层的位置是*都不能通过。
2、从一层到另一层只能通过时空传送机
#include
#include
#include
using namespace std;
char map[11][11][11];
int vis[11][11][11];
int n,m,t;
struct node
{
int x,y,z;
int time;
friend bool operator < (node a,node b)
{
return a.time>b.time;
}
};
int judge(int r,int c,int d)
{
if(r<0||r>=2||c<0||c>=n||d<0||d>=m)
return 0;
if(map[r][c][d]=='*'||vis[r][c][d])
return 0;
return 1;
}
int bfs()
{
int i,j;
int move[4][2]={0,1,0,-1,1,0,-1,0};
priority_queueq;
node beg,end;
beg.x=0;
beg.y=0;
beg.z=0;
beg.time=0;
q.push(beg);
vis[0][0][0]=1;
while(!q.empty())
{
end=q.top();
q.pop();
if(map[end.x][end.y][end.z]=='P')
{
if(end.time<=t)
return 1;
return 0;
}
if(map[end.x][end.y][end.z]=='#')
{
beg.x=1-end.x;
beg.y=end.y;
beg.z=end.z;
beg.time=end.time;
if(judge(beg.x,beg.y,beg.z)&&map[beg.x][beg.y][beg.z]!='#')
{
q.push(beg);
}
}
else
for(i=0;i<4;i++)
{
beg.x=end.x;
beg.y=end.y+move[i][0];
beg.z=end.z+move[i][1];
if(judge(beg.x,beg.y,beg.z))
{
vis[beg.x][beg.y][beg.z]=1;
beg.time=end.time+1;
q.push(beg);
}
}
}
return 0;
}
int main()
{
int i,j,k,o;
scanf("%d",&o);
while(o--)
{
memset(vis,0,sizeof(vis));
scanf("%d%d%d",&n,&m,&t);
for(k=0;k<2;k++)
{
for(i=0;i
scanf("%s",map[k][i]);
}
if(bfs()) printf("YES\n");
else printf("NO\n");
}
return 0;
}
HDOJ 2102 A计划(bfs)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102 思路分析: <1>搜索方法分析:由于需要寻找最短的找到公主的路径,所以采用bfs搜索 ...
BFS HDOJ 2102 A计划
题目传送门 题意:中文题面 分析:双层BFS,之前写过类似的题.总结坑点: 1.步数小于等于T都是YES 2. 传送门的另一侧还是传送门或者墙都会死 3. 走到传送门也需要一步 #include &l ...
hdu 2102 A计划
题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=2102 A计划 Description 可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸 ...
hdoj 2102 A计画 【BFS】
称号:hdoj 2102 A计画点击打开链接 意甲冠军:文的就不说了.求救出公主所须要的最短时间,所以用广搜. 分析:读题之后不难做,比一般的题目多了一个条件就是能够传送,那么我们能够在广搜里面加一个 ...
HDU 2102 A计划(两层地图加时间限制加传送门的bfs)
传送门: http://acm.hdu.edu.cn/showproblem.php?pid=2102 A计划 Time Limit: 3000/1000 MS (Java/Others) Me ...
【HDOJ】2102 A计划
BFS,不过有很多地方需要注意,比如传送机传送到另一个传送机.还有要注意格式. #include #include #include & ...
hdu - 2102 A计划 (简单bfs)
http://acm.hdu.edu.cn/showproblem.php?pid=2102 题目还是不难,注意起点一定是(0,0,0),然后到达P点时间<=t都可以. 用一个3维字符数组存储图 ...
hdu 2102 A计划(优先队列+dfs)
改了好久,上午来实验室打出来了,运行就是不对,一直找啊找!还是没找到,最后突然停电了,打好的代码还没保存呢! 刚才来的时候又重新打了一遍!!!结果一个小小的错误wrong了好久!!! 在dfs值返回时 ...
hdu 2102 A计划(双层BFS)(具体解释)
转载请注明出处:http://blog.csdn.net/u012860063?viewmode=contents 题目链接:http://acm.hdu.edu.cn/showproblem.php ...
随机推荐
12月5日PHPCMS替换主页
cms替换主页的步骤 1.先做好静态页面: 2.在D:\wamp\www\phpcms\install_package\phpcms\templates文件夹下建新的文件夹tianqiwangluo( ...
关于StdAfx.h和StdAfx.cpp
http://www.cplusplus.com/articles/2z86b7Xj/ https://msdn.microsoft.com/en-us/library/h552b3ca.aspx h ...
javac 命令
HelloWorld.java:1: 需要为 class.interface 或 enum 锘缝ublic class HelloWorld{ ^ 1 错误 这个错误出现的原因主要是在中文操作系统中, ...
LR 常见问题总结
问题1:Error: Two Way Communication Error: Function two_way_comm_post_message/two_way_comm_p ...
解决 lispbox macOS 不兼容问题
误打误撞,解决了很重要的入门级问题,简要记录下. lispbox 官网末尾说目前暂不兼容 10.4 以上系统: TODO: Compile on Mac OS X 10.4, for compatab ...
vuex状态管理,state,getters,mutations,actons的简单使用(一)
之前的文章中讲过,组件之间的通讯我们可以用$children.$parent.$refs.props.data... 但问题来了,假如项目特别大,组件之间的通讯可能会变得十分复杂... 这个时候了我们 ...
python pickle 模块的使用
用于序列化的两个模块 json:用于字符串和Python数据类型间进行转换 pickle: 用于python特有的类型和python的数据类型间进行转换 json提供四个功能:dumps,dump,l ...
Pycharm数据库连接错误
简单地总结就一句话: Python2的mysql库为:mysqldb,而Python3的为:pymysql. 当我们使用Pycharm开发项目时,首先需要下载安装相对应的数据库,以及在项目根目录下的s ...
09--STL关联容器(map/multimap)
一:map/multimap的简介 map是标准的关联式容器,一个map是一个键值对序列,即(key,value)对.它提供基于key的快速检索能力. map中key值是唯一的.集合中的元素按一定的顺 ...
hashlib 和 hmac 算法的区别
-----md5 = hashlib.md5() md5.update(password+salt) md5.hexdigest() ----- h = hmac.new(key,password,d ...
