题目链接:http://poj.org/problem?id=2251
题目大意
你被困在了一个三维的迷宫,找出能通往出口的最短时间。如果走不到出口,输出被困。
思路
由于要找最短路径,其实就是BFS。一般的BFS是前后左右四个方向,这个题相当于是变成能往上下左右前后六个方向找。修改一下二维BFS搜索部分的代码即可。
题解
#include <iostream>
#include <queue>
#include<fstream>
#include <cstring>
//#define debug
using namespace std; char a[][][];
int vis[][][];
int x,y,z; //范围 int d1[] = {,-,,,,};
int d2[] = {,,,-,,};
int d3[] = {,,,,,-}; struct point{
int x;
int y;
int z;
int step;
}p1,p2,e; bool isValid(point p){
if(p.x>= && p.x<x && p.y>= && p.y<y && p.z>= && p.z<z && (a[p.x][p.y][p.z] == '.' || a[p.x][p.y][p.z] == 'E' )&& vis[p.x][p.y][p.z] == ){
return true;
}
return false;
} bool success(point p){
if(p2.x == e.x && p2.y == e.y && p2.z == e.z){
return true;
}
return false;
} void bfs(){
point tmp;
queue<point> q;
q.push(p1);
while(!q.empty()){
p2 = q.front();
q.pop();
if(success(p2)){
return;
}else{
for(int ii=;ii<;ii++){ //向六个方向搜索
tmp.x = p2.x+d1[ii];
tmp.y = p2.y+d2[ii];
tmp.z = p2.z+d3[ii];
if(isValid(tmp)){
tmp.step = p2.step+;
vis[tmp.x][tmp.y][tmp.z]= ;
q.push(tmp);
}
}
}
}
} int main()
{
#ifdef debug
//cin重定向
ifstream cin("C:\\Users\\Administrator\\Desktop\\test.txt");
#endif while((cin >> x >> y >> z)){
if(x == ){
break;
}
for(int i = ;i < x;i++){ //读入maze
for(int j = ;j < y;j++){
for(int k = ;k < z;k++){
cin >> a[i][j][k];
if(a[i][j][k] == 'S'){
p1.x = i;
p1.y = j;
p1.z = k;
p1.step = ;
}else if(a[i][j][k] == 'E'){
e.x = i;
e.y = j;
e.z = k;
}
}
}
} memset(vis,,sizeof(vis)); //初始化vis bfs();
if(p2.x == e.x && p2.y == e.y && p2.z == e.z){
cout << "Escaped in " << p2.step << " minute(s)." << endl;
}else{
cout << "Trapped!" << endl;
}
}
}