UVa532 Dungeon Master 三维迷宫-白红宇

UVa532 Dungeon Master 三维迷宫

阅读量：6463 次

发布时间：2019-06-23

本文共 2507 字，大约阅读时间需要 8 分钟。

学习点：

scanf可以自动过滤空行

搜索时要先判断是否越界（L R C），再判断其他条件是否满足

bfs搜索时可以在入口处（push时）判断是否达到目标，也可以在出口处（pop时）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=31;const int dl[]={-1, 1, 0, 0, 0, 0};const int dr[]={
   0, 0, -1, 1, 0, 0};const int dc[]={
   0, 0, 0, 0, -1, 1};struct State {    State(int l, int r, int c, int d): l(l), r(r), c(c), d(d) {}    int l, r, c;    int d;};int L, R, C;int SL, SR, SC;int EL, ER, EC;typedef char A[N][N][N];A dungeon, vis;int bfs() {    if(SL==EL && SR==EL && SC==EC) return 0;    State s(SL, SR, SC, 0); vis[SL][SR][SC]=1;    queue
          
            q; q.push(s); while(!q.empty()) { State t=q.front(); q.pop(); //可以在出口判断 //if(t.l==EL && t.r==ER && t.c==EC) return t.d; for(int i=0;i<6;i++) { int nl=t.l+dl[i]; int nr=t.r+dr[i]; int nc=t.c+dc[i]; if(nl>=0 && nl
           
            =0 && nr
            
             =0 && nc

// UVa532 Dungeon Master// Rujia Liu// 题意：三维迷宫中给定起点（字符S）和终点（字符E），墙是'#'，空格是'.'，求最短路长度#include
     
      #include
      
       #include
       
        using namespace std;struct State {  int l, r, c;  State(int l, int r, int c):l(l),r(r),c(c) {}};const int maxn = 30 + 5;const int dl[] = {
   1,-1,0,0,0,0};const int dr[] = {
   0,0,1,-1,0,0};const int dc[] = {
   0,0,0,0,1,-1};int L, R, C, d[maxn][maxn][maxn], vis[maxn][maxn][maxn];char maze[maxn][maxn][maxn];int bfs(int l1, int r1, int c1) {  queue
        
          Q;  d[l1][r1][c1] = 0;  vis[l1][r1][c1] = 1;  Q.push(State(l1, r1, c1));  while(!Q.empty()) {    State s = Q.front(); Q.pop();    for(int i = 0; i < 6; i++) {      int newl = s.l + dl[i];      int newr = s.r + dr[i];      int newc = s.c + dc[i];      if(newl >= 0 && newl < L && newr >= 0 && newr < R && newc >= 0 && newc < C && maze[newl][newr][newc] != '#' && !vis[newl][newr][newc]) {        Q.push(State(newl, newr, newc));        vis[newl][newr][newc] = 1;        d[newl][newr][newc] = d[s.l][s.r][s.c] + 1;        if(maze[newl][newr][newc] == 'E') return d[newl][newr][newc];      }    }  }  return -1;}int main() {  while(scanf("%d%d%d", &L, &R, &C) == 3 && L) {    int l1, r1, c1;    for(int i = 0; i < L; i++)      for(int j = 0; j < R; j++) {        scanf("%s", maze[i][j]);        for(int k = 0; k < C; k++)          if(maze[i][j][k] == 'S') { l1 = i; r1 = j; c1 = k; }      }    memset(vis, 0, sizeof(vis));    int ans = bfs(l1, r1, c1);    if(ans >= 0) printf("Escaped in %d minute(s).\n", ans);    else printf("Trapped!\n");  }  return 0;}