首页 > 代码库 > hdu 2102 A计划(双层BFS)(具体解释)
hdu 2102 A计划(双层BFS)(具体解释)
转载请注明出处:http://blog.csdn.net/u012860063?viewmode=contents
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102
Problem Description
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主,由于他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚,告招天下勇士来解救公主。只是公主早已习以为常,她深信智勇的骑士LJ肯定能将她救出。
现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是S(0,0,0),公主的位置用P表示,时空传输机用#表示,墙用*表示,平地用.表示。骑士们一进入时空传输机就会被转到还有一层的相对位置,但假设被转到的位置是墙的话,那骑士们就会被撞死。骑士们在一层中仅仅能前后左右移动,每移动一格花1时刻。层间的移动仅仅能通过时空传输机,且不须要不论什么时间。
现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是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.有可能起点和终点在同一层,例子是分别在两层里。起点和终点能够在随意的位置。
3.两边都是传送门时,或者一边是传送门一边是墙时,这两种情况是死路。
4.输入时要注意两张地图间有空行,要特殊处理。
*/
代码例如以下:
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include <iostream> using namespace std; #define M 17 int xx[4]={1,0,0,-1}; int yy[4]={0,1,-1,0}; int x,y,z; int n, m, ttime; char map[2][M][M]; int vis[2][M][M];//标记 struct node { int x, y, z; int Time; }; //q.push(front); void bfs() { int i; int dx, dy, dz; queue<node>q; node front, rear; memset(vis,0,sizeof(vis)); front.x = x,front.y=y,front.z=z; front.Time = 0; vis[z][x][y] = 1; q.push(front);//若这个定义在外面则必须每次清空 while(!q.empty()) { front = q.front(); q.pop(); for(i = 0; i < 4; i++) { dx = front.x+xx[i]; dy = front.y+yy[i]; dz = front.z; //推断是否越界,目标点是否为墙,是否超时 if(dx>=0&&dx<n&&dy>=0&&dy<m&&!vis[dz][dx][dy] &&map[dz][dx][dy]!='*'&&front.Time<ttime) { if(map[dz][dx][dy]=='#' && !vis[dz][dx][dy]) {//表示遇到传送器的情况 vis[dz][dx][dy] = 1; if(front.z == 1)//假设在上层,就传到下层 dz = 0; else if(front.z == 0)//假设在下层,就传到上层 dz = 1; } vis[dz][dx][dy] = 1; if(map[dz][dx][dy] == 'P')//找到公主 { printf("YES\n"); return; } rear.x = dx,rear.y = dy; rear.z = dz,rear.Time=front.Time+1; q.push(rear); } } } printf("NO\n"); } int main() { int c; int i, j, k; while(~scanf("%d",&c)) { while(c--) { // while(!q.empty()) // q.pop(); // scanf("%d%d%d",&n,&m,&ttime); cin >> n >> m >> ttime; for(k = 0; k < 2; k++) { for(i = 0; i < n; i++) { // scanf("%s",map[k][i]); for(j = 0; j < m; j++) { cin>>map[k][i][j]; if(map[k][i][j] == 'S') { x = i, y = j, z = k; } } } } for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { if(map[0][i][j]=='#' && map[1][i][j]=='*') {//假设传送机上方是墙,他就会撞死。。。。 //所以这样的情况也要排除。 map[0][i][j] = '*'; } if(map[0][i][j]=='*' && map[1][i][j]=='#') {//假设传送机下方是墙,相同他会撞死,也排除 map[1][i][j] = '*'; } if(map[0][i][j]=='#' && map[1][i][j]=='#') {//假设传送机上方还是传送机,就会陷入死循环, //所以这样的情况我们把上下相应的两个位置设为墙. map[0][i][j] = '*',map[1][i][j] = '*'; } } } bfs(); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。