HDU 2102 (BFS三维数组)

本文主要是介绍HDU 2102 (BFS三维数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在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

首先地图是个两块，需要用到三维地图，做惯了二维的，不知道怎么写三维的BFS，今天我就教教大家，怎么写三维地图的BFS，后续再写三维DFS。

与二维一样，都需要用到队列 queue 和结构体的结合，来装各个点的x ,y, 楼层，时间。有点不一样的是，在楼层之间的互相转化有些麻烦，相比于二位地图在楼层之间来回切换，直接三维数组，在切换楼层点时，直接将那个楼层的点判断是否（越出地图），直接可以加到队列中，然后在处理这个点时，就根据楼层，在不同的楼层之间处理数据，就不用在单独一个再去搜索，也很麻烦，不好实现。在不遇到切换点时，就直接用套路，四个方向去搜索，加入到队列中，一个一个去判断，直到找到那个点为止。

在每个点判断一次，是否点越界，也要进行点标记，不然爆掉了栈。

总结：一开始做时直接想怎么去一个转换楼层点，用最短时间去救公主，但是情况还是太多，不能找到一个具体的搜索策略，还是得依靠广搜，每个点的四个方向都去一遍，也可以从一层转到一层，去搜索，还是可以搜索到很多情况，直到找到公主的坐标。第一次接触三维地图，有些蒙圈。

看看代码 :学习

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<bits/stdc++.h>
#include<algorithm>
const int maxn=55;
typedef long long ll;
using namespace std;
#include<queue>char  maap[maxn][maxn][maxn];
bool vis[maxn][maxn][maxn];int n,m,yaoqiutime;typedef struct node
{int x;int y;int floor;int time;
}point;int a[]={0,0,1,-1};
int b[]={1,-1,0,0};bool judge(int lou,int x,int y)
{if(maap[lou][x][y]=='*'||vis[lou][x][y]||x<0||y<0||x>=n||y>=m)return false;return true;
}int  bfs()
{queue<point>mp;point s;s.x=s.y=0;s.floor=1;s.time=0;vis[1][0][0]=1;mp.push(s);while(!mp.empty()){point q=mp.front();mp.pop();if(maap[q.floor][q.x][q.y]=='P'&&q.time<=yaoqiutime)return 1;else if(maap[q.floor][q.x][q.y]=='P'&&q.time>yaoqiutime)return -1;if(maap[q.floor][q.x][q.y]=='#'){point s1;s1.x=q.x;s1.y=q.y;s1.time=q.time;if(q.floor==1){if(judge(q.floor+1,q.x,q.y)){s1.floor=q.floor+1;mp.push(s1);vis[s1.floor][s1.x][s1.y]=1;}}	else{if(judge(q.floor-1,q.x,q.y)){s1.floor=q.floor-1;mp.push(s1);vis[s1.floor][s1.x][s1.y]=1;}}}else{for(int i=0;i<4;i++){point s2;s2.floor=q.floor;s2.x=q.x+a[i];s2.y=q.y+b[i];s2.time=q.time+1;if(judge(s2.floor,s2.x,s2.y)){mp.push(s2);vis[s2.floor][s2.x][s2.y]=1;}	}}	}return -1;
}int main()
{int t;cin>>t;int i,j,k;while(t--){memset(vis,0,sizeof(vis));cin>>n>>m>>yaoqiutime;for(k=1;k<=2;k++)				for(i=0;i<n;i++)							for(j=0;j<m;j++)cin>>maap[k][i][j];int res=bfs();if(res==-1)cout<<"NO"<<endl;elsecout<<"YES"<<endl;}return 0;}