# uva 532 Dungeon Master —— BFS(求最短路)

``````/**

uva —— 532 —— Dungeon Master

--------------------------------------

input:

3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0

output

Escaped in 11 minute(s).
Trapped!
*/

#include iostream
#include cstring
#include queue
#define maxn 31

using namespace std;

typedef struct node{
int l;
int r;
int c;
}Node;

int L,R,C;
char G[maxn][maxn][maxn];
int visited[maxn][maxn][maxn];
int dist[maxn][maxn][maxn];
Node start_node;
queueNode q;

int INF = 27100;//!因为30*30*30，最多有27000的长度。
bool successed;
int _time;//!注意不能命名为"time",原因不明。否则将出现错误：cannot convert 'int' to 'time_t(time_t*) throw () {aka long int(long int*) throw ()}

bool check(int l,int r,int c){
if(l = 0  l = L-1  r = 0  r = R-1  c = 0  c = C-1){
if((G[l][r][c] == '.' || G[l][r][c] == 'E')   !visited[l][r][c]){
return true;
}
}

return false;
}

//!         前后左右上下
int dL[8] = { 0,0,  0,0,  1,-1};
int dR[8] = {-1,1,  0,0,  0, 0};
int dC[8] = { 0,0, -1,1,  0, 0};

void bfs(){
visited[start_node.l][start_node.r][start_node.c] = 1;
dist[start_node.l][start_node.r][start_node.c] = 0;
q.push(start_node);

while(!q.empty()){
Node u = q.front();
q.pop();

for(int i = 0; i  6;i ++){
int l2 = u.l + dL[i];
int r2 = u.r + dR[i];
int c2 = u.c + dC[i];

if(check(l2,r2,c2)){
visited[l2][r2][c2] = 1;
dist[l2][r2][c2] = dist[u.l][u.r][u.c] + 1;

if(G[l2][r2][c2] == 'E'){
successed = true;
_time = dist[l2][r2][c2];
return ;
}

Node v;
v.l = l2; v.r = r2; v.c = c2;
q.push(v);
}

}

}
}

void input(){
memset(G,'#',sizeof(G));
memset(visited,0,sizeof(visited));
memset(dist,0,sizeof(dist));
while(!q.empty()) q.pop();

successed = false;
_time = INF;

for(int l = 0; l  L; l++){//层数
for(int r = 0; r  R; r ++){//行数
for(int c = 0; c  C; c ++){//列数
cinG[l][r][c];

if(G[l][r][c] == 'S'){
start_node.l = l;
start_node.r = r;
start_node.c = c;
}
}
}
}
}

int main(){
while(cinLRC){
if(!L!R!C) break;

input();

bfs();

if(successed){
cout"Escaped in "_time" minute(s)."endl;
}else{
cout"Trapped!"endl;
}
}

return 0;
}
/**

————三维立体图的遍历

对这一种有某个目的点的问题，在写check()时，终点也是可以通行的点。

*/
``````

``````/**

*/
#include iostream
#include cstring

#define maxn 31

using namespace std;
char G[maxn][maxn][maxn];
int visited[maxn][maxn][maxn];
int L,R,C;

int INF = 27100;//!因为30*30*30，最多有27000的长度。

bool successed;
int _time;//!注意不能命名为"time",原因不明。否则将出现错误：cannot convert 'int' to 'time_t(time_t*) throw () {aka long int(long int*) throw ()}
int nowTime;
int s_L,s_R,s_C;

bool check(int l,int r,int c){
if(l = 0  l = L-1  r = 0  r = R-1  c = 0  c = C-1){
if((G[l][r][c] == '.' || G[l][r][c] == 'E')   !visited[l][r][c]){
if(nowTime  _time) return true;
}
}

return false;
}
//!         前后左右上下
int dL[8] = { 0,0,  0,0,  1,-1};
int dR[8] = {-1,1,  0,0,  0, 0};
int dC[8] = { 0,0, -1,1,  0, 0};

void dfs(int l,int r,int c){
if(G[l][r][c] == 'E'){
successed = true;
if(nowTime  _time) _time = nowTime;

return ;
}

for(int i = 0; i  6;i ++){
int l2 = l + dL[i];
int r2 = r + dR[i];
int c2 = c + dC[i];

if(check(l2,r2,c2)){
visited[l2][r2][c2] = 1;
nowTime ++;

dfs(l2,r2,c2);

visited[l2][r2][c2] = 0;
nowTime --;
}
}
}

void input(){
memset(G,'#',sizeof(G));
memset(visited,0,sizeof(visited));

successed = false;
_time = INF;
nowTime = 0;

for(int l = 0; l  L; l++){//层数
for(int r = 0; r  R; r ++){//行数
for(int c = 0; c  C; c ++){//列数
cinG[l][r][c];

if(G[l][r][c] == 'S'){
s_L = l;
s_R = r;
s_C = c;
}
}
}
}

}

int main(){
while(cinLRC){
if(!L!R!C) break;

input();

dfs(s_L,s_R,s_C);

if(successed){
cout"Escaped in "_time" minute(s)."endl;
}else{
cout"Trapped!"endl;
}
}

return 0;
}
``````

• 星秀
• 03:51
• 00:59
• 05:59