文章目录
题目大意
三维迷宫中有墙(X)，路(.)，起点(S)，终点(E), 问终点是否可达，若可达最早什么时候可达。
解题思路
- (1) 最短时间到达，直接BFS。
- (2) 注意
grad[z][x][y]，第一维代表纵坐标。 - (3) BFS用优先队列较好。
代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 35;
struct Node
{
int x,y,z,t;
bool operator < (const Node &A)const{
return t > A.t;
}
}tmp;
priority_queue<Node, vector<Node> >PQ;
char grad[MAX][MAX][MAX];
int visited[MAX][MAX][MAX];
int dir[6][3] = {{1,0,0},{0,1,0},{0,0,1},{-1,0,0},{0,-1,0},{0,0,-1}};
int L, n, m;
int bfs(int sx, int sy, int sz)
{
while(!PQ.empty())
PQ.pop();
memset(visited, 0, sizeof(visited));
tmp.x = sx;
tmp.y = sy;
tmp.z = sz;
tmp.t = 0;
PQ.push(tmp);
while(!PQ.empty())
{
Node top = PQ.top();
PQ.pop();
//cout << top.x << " " << top.y << " " << top.z << endl;
visited[top.z][top.x][top.y] = 1;
for(int i=0; i<6; i++)
{
int nx = top.x + dir[i][0];
int ny = top.y + dir[i][1];
int nz = top.z + dir[i][2];
if(nx < 0 || nx >=n || ny < 0 || ny >= m || nz < 0 || nz >= L)
continue;
if(visited[nz][nx][ny])
continue;
if(grad[nz][nx][ny] == '#')
continue;
if(grad[nz][nx][ny] == 'E')
return top.t + 1;
tmp.x = nx;
tmp.y = ny;
tmp.z = nz;
tmp.t = top.t+1;
visited[nz][nx][ny] = 1;
PQ.push(tmp);
}
}
return -1;
}
int main()
{
int sx, sy, sz;
while(cin >> L >> n >> m)
{
if(L == 0 && n == 0 && m == 0)
break;
for(int i=0; i<L; i++)
{
for(int j=0; j<n; j++)
{
for(int k=0; k<m; k++)
{
cin >> grad[i][j][k];
if(grad[i][j][k] == 'S')
{
sx = j;
sy = k;
sz = i;
}
}
}
}
int ans = bfs(sx, sy, sz);
if(ans == -1)
cout << "Trapped!" << endl;
else
cout << "Escaped in "<<ans<<" minute(s)." << endl;
}
return 0;
}