A计划
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4022 Accepted Submission(s): 911
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
说一下这道题,题目意思是:骑士去救公主,要走一个两层迷宫。迷宫有里面有传送器,能通过另外一层的同一地点,若该地点是石头,则会撞死。注意一点,传送器第二层也可能有,有可能需要1or2层之间来回传送,才能救到公主,这里只需要开一个3维数组进行标记就可以了。
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
int xx[4] = {1, -1, 0, 0};
int yy[4] = {0, 0, 1, -1};
int map[2][15][15]; //三维数组:第一维为层数
char a[2][15][15];
int N, M, T, x1, y1, x2, y2;
bool flag;
struct node
{
int x, y, z, step; //(x,y)是坐标,z是第几层,step是步数
}n, m;
int main()
{
int i, j, k, t;
scanf("%d", &t);
while(t--)
{
scanf("%d %d %d", &N, &M, &T);
for(k = 0; k < 2; k++)
{
for(i = 0; i < N; i++)
{
for(j = 0; j < M; j++)
{
cin>>a[k][i][j];
map[k][i][j] = 10000; //初始化所有标记
}
}
}
flag = false;
n.x = n.y = n.z = n.step = 0;
map[0][0][0] = 0;
queue<node> Q; //建立队列
Q.push(n);
while(!Q.empty())
{
m = Q.front();
Q.pop();
if(a[m.z][m.x][m.y] == 'P') //到达终点
{
flag = true;
break;
}
for(i = 0; i < 4; i++)
{
n.x = m.x + xx[i];
n.y = m.y + yy[i];
if(n.x>=0 && n.x<N && n.y>=0 && n.y<M)
{
n.step = m.step + 1; //更新改点情况
n.z = m.z;
if(a[n.z][n.x][n.y] == '*') continue; //该点不可行,不行
if(n.step > T) continue; //时间已超过,不行
if(a[n.z][n.x][n.y] == '#') //若该点是传送器
{
//先判断传送后的地点是否可行,这里用了^1的方法,0变1,1变0
if(a[n.z^1][n.x][n.y] == '*' || a[n.z^1][n.x][n.y] == '#') continue;
//判断该点步数是否超过该点之前的步数
if(n.step >= map[n.z][n.x][n.y]) continue;
map[n.z][n.x][n.y] = n.step; //更新该点步数
map[n.z^1][n.x][n.y] = n.step; //另外一层的步数都改
n.z ^= 1; //该点属第几层也改变
Q.push(n);
}
else
{
//判断该点步数是否超过该点之前的步数
if(n.step >= map[n.z][n.x][n.y]) continue;
map[n.z][n.x][n.y] = n.step; //更新该点步数
Q.push(n);
}
}
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
分享到:
相关推荐
hdu_2102_passed_sorce
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
HDU最全ac代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu动态规划算法集锦
hdu题目分类