NYOJ 353 3D Dungeon(三维bfs)

       这道题是三维地图去找最短路，所以类比着二维地图的广搜过程做就行了，只用在搜索方向上做点改变。

AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct Node{
  int x,y,z,step;
}Next,Now,S,E;
char MAP[35][35][35];
int vis[35][35][35];
int l,r,c;
int dir[6][3] = {1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};    // 三维地图的六个方向

int bfs(){
  queue<Node> q;
  S.step = 0;
  memset(vis,0,sizeof(vis));
  q.push(S);
  while(!q.empty()){
    Now = q.front();
    q.pop();
    if(Now.x == E.x &&Now.y == E.y &&Now.z == E.z){
      return Now.step;
    }
    for(int i=0;i<6;i++){           // 类比二维地图 在这里稍微改变下就行了
      Next.x = Now.x + dir[i][0];
      Next.y = Now.y + dir[i][1];
      Next.z = Now.z + dir[i][2];
      if(Next.x>=0&&Next.y>=0&&Next.z>=0&&Next.x<l&&Next.y<r&&Next.z<c&&MAP[Next.x][Next.y][Next.z]!='#'&&vis[Next.x][Next.y][Next.z]==0){
        vis[Next.x][Next.y][Next.z] = 1;
        Next.step = Now.step + 1;
        q.push(Next);
      }
    }
  }
  return -1;

}
int main()
{
  while(~scanf("%d%d%d",&l,&r,&c)){
    if(l==0&&r==0&&c==0) break;
    memset(MAP,0,sizeof(MAP));
    for(int i=0;i<l;i++){              // 初始化地图
      for(int j=0;j<r;j++){
        for(int k = 0;k<c;k++){
          cin>>MAP[i][j][k];
          if(MAP[i][j][k]=='S'){       // 标记起点
            S.x = i;
            S.y = j;
            S.z = k;
          }
          if(MAP[i][j][k]=='E'){       // 标记终点
            E.x = i;
            E.y = j;
            E.z = k;
          }
        }
      }
    }
    int temp = bfs();
    if(temp == -1){
      cout<<"Trapped!"<<endl;
    }
    else {
      cout<<"Escaped in "<<temp<<" minute(s)."<<endl;
    }
  }
  return 0;
}
/***
   [来源] NYOJ 353
   [题目] 3Ddungeon
   [思路]
      这是一道三维搜索题，也不是很难，类比二维地图去做就好了。
   [输入]
      3 4 5
      S....
      .###.
      .##..
      ###.#

      #####
      #####
      ##.##
      ##...

      #####
      #####
      #.###
      ####E

      1 3 3
      S##
      #E#
      ###

      0 0 0
   [输出]
      Escaped in 11 minute(s).
      Trapped
*/