POJ.2251 Dungeon Master （三维BFS）
题意分析
你被困在一个3D地牢中且继续寻找最短路径逃生。地牢由立方体单位构成，立方体中不定会充满岩石。向上下前后左右移动一个单位需要一分钟。你不能对角线移动并且迷宫四周坚石环绕。
若能逃离，则输出逃离需要的最短时间，否则输出Trapped!。
与二维BFS的差别在于，多了一个上下两层。所以除了先后左右移动，还要有上下移动，对于每个位置，总共有6种移动方式，将6种移动方式种可行的每次塞进队列里面就好了。
依旧还要记录歩数。此题没什么大坑。
代码总览
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define nmax 30
using namespace std;
char mp[nmax][nmax][nmax];
bool visit[nmax][nmax][nmax];
int Slevel,Sx,Sy,Elevel,Ex,Ey;
int spx[4] = {0,1,0,-1};
int spy[4] = {1,0,-1,0};
int spl[2] = {-1,1};
bool isout = false;
int l,r,c,ans;
typedef struct mes{
int level;
int x;
int y;
int steps;
}mes;
void changeVisit(mes temp)
{
visit[temp.level][temp.x][temp.y] = true;
return;
}
bool check(mes temp)
{
if(temp.level >= l || temp.level <0 || temp.x <0 || temp.x>=r || temp.y<0 || temp.y>=c || visit[temp.level][temp.x][temp.y] || mp[temp.level][temp.x][temp.y] == '#')
return false;
return true;
}
void bfs()
{
queue<mes> q;
while(!q.empty()) q.pop();
mes sta = {Slevel,Sx,Sy,0},temp,head;
q.push(sta);
changeVisit(sta);
while(!q.empty()){
head = q.front();q.pop();
if(head.level == Elevel && head.x == Ex && head.y == Ey){
isout = true;
ans = head.steps;
break;
}
for(int i = 0;i<4;++i){
temp.level = head.level;
temp.x = head.x + spx[i];
temp.y = head.y + spy[i];
temp.steps = head.steps + 1;
if(check(temp)){
q.push(temp);
changeVisit(temp);
}
}
for(int i = 0;i<2;++i){
temp.level = head.level + spl[i];
temp.x = head.x;
temp.y = head.y;
temp.steps = head.steps + 1;
if(check(temp)){
q.push(temp);
changeVisit(temp);
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d %d %d",&l,&r,&c) != EOF){
if( l == 0 && r == 0 && c == 0) break;
isout = false;
memset(mp,0,sizeof(mp));
memset(visit,0,sizeof(mp));
for(int i = 0;i<l;++i){
for(int j = 0;j<r;++j){
scanf("%s",mp[i][j]);
for(int k = 0;k<c;++k){
if(mp[i][j][k] == 'S'){
Slevel = i; Sx = j; Sy = k;
}else if(mp[i][j][k] == 'E'){
Elevel = i; Ex = j; Ey = k;
}
}
}
}
bfs();
if(isout == true){
printf("Escaped in %d minute(s).\n",ans);
}else{
printf("Trapped!\n");
}
}
return 0;
}
