2013程序设计实现之广搜作业 B

/**

***= =最近懒得没有发表一篇文章，自觉羞愧...于是发表几篇小文以弥胡哥对我的期盼之情...

翻译一下： 一个房间，3维的，指定他的3个维度的大小，然后指定他的每个单位的内容（= =w 天哪poj你好烦），#代表该单位无法通过，.代表可以通过，S代表可怜的主人公所在位置，E代表光明的出口所在的位置。求该主人公能否逃脱，能在最少多少次的操作后逃脱（话说这题翻译过来是地下城...好吧，槽点略多）

描述
You are trapped in a 3D dungeon and need to find the quickest way out!
 The dungeon is composed of unit cubes which may or may not be filled with rock.
  It takes one minute to move one unit north, south, east, west, up or down.
   You cannot move diagonally and the maze is surrounded by solid rock on all sides.

Is an escape possible? If yes, how long will it take?
输入
The input consists of a number of dungeons.
 Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon.
 A cell full of rock is indicated by a '#' and empty cells are represented by a '.'.
  Your starting position is indicated by 'S' and the exit by the letter 'E'.
  There's a single blank line after each level.
   Input is terminated by three zeroes for L, R and C.
输出
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form
Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!

 

样例输入
3 4 5
S....
.###.
.##..
###.#

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

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

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

0 0 0
样例输出
Escaped in 11 minute(s).
Trapped!
*/
#include<iostream>
#include<string.h>
#include<string>
#include<queue>
using namespace std;
//

class Point{
      public:
             Point(int x,int y,int z){
                       this->x = x;
                       this->y = y;
                       this->z = z;
                       }
            
             bool equals(Point p){
                  return (x==p.x && y==p.y && z==p.z);
                  }
             int x;
             int y;
             int z;
      };
void test(int L,int R,int C){
     if(L<=30 && R<=30 && C<=30){//万恶的英语，题目limit to是<=的意思
            
            
                          int ROOM[L][R][C];
                          int NUMofS = 0;//S的个数
                          int NUMofE = 0;//E的个数
                          bool able = true;//此属性决定了该输入能否进行，包含了格式输出错误，个数错误等情况
                          int x0,y0,z0;//主人公的位置
                          int x1,y1,z1;  //出口的位置
                          string s;
                          memset(ROOM,0,sizeof(ROOM));//将所有的内容都赋予0值
                          for(int i = 0;i < L;i++){
                                  for(int j = 0;j < R;j++){
                                          cin>>s;
                                          if(s.length()>C)able = false;
                                          for(int k = 0;k < C;k++){
                                                  char ch = s.at(k);//通过输入的字符来决定该位置的内容值
                                                  switch(ch){
                                                                 case '#' :
                                                                      ROOM[i][j][k] = -1;//-1即无法通过
                                                                      break;
                                                                 case '.' ://可以通过，默认为0
                                                                      break;
                                                                 case 'S' :
                                                                      x0 = i;
                                                                      y0 = j;
                                                                      z0 = k;
                                                                      NUMofS++;
                                                                      if(NUMofS>1)
                                                                          able = false;
                                                                      break;
                                                                 case 'E' :
                                                                      x1 = i;
                                                                      y1 = j;
                                                                      z1 = k;
                                                                      NUMofE++;
                                                                      if(NUMofE>1)
                                                                          able = false;
                                                                      break;
                                                                 default :
                                                                      able = false;
                                                                 }
                                                  }
                                          }
                                  }
                                  if(able == false){//感觉题目设置的不严谨，因为输入格式错误的话，题目没有说明要怎么解决，不过经过多次的wa测试，上述情况应该输出无法通过的语句
                                          cout<<"Trapped!"<<endl;
                                          return;
                                          }
                                 
                                  Point from(x0,y0,z0);
                                  Point to(x1,y1,z1);
                                 
                                  queue<Point> p;
                                  p.push(from);
                                  while(!p.empty()){
                                           Point xp = p.front();
                                           p.pop();
                                           if(xp.equals(to)){//搜到了相同的点就输出
                                                cout<<"Escaped in "<<ROOM[to.x][to.y][to.z]<<" minute(s)."<<endl;
                                                return;
                                                }else{
                                                      for(int i = 0;i < 6;i++){
                                                              switch(i){
                                                                        case 0 ://x方向-1
                                                                             if(xp.x-1>=0 && !ROOM[xp.x-1][xp.y][xp.z]){
                                                                                          Point np(xp.x-1,xp.y,xp.z);
                                                                                          if(!np.equals(from)){
                                                                                              p.push(np);
                                                                                              ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
                                                                                              }
                                                                                          }
                                                                                          break;
                                                                        case 1 ://x方向+1
                                                                             if(xp.x+1<L && !ROOM[xp.x+1][xp.y][xp.z]){
                                                                                          Point np(xp.x+1,xp.y,xp.z);
                                                                                          if(!np.equals(from)){
                                                                                              p.push(np);
                                                                                              ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
                                                                                              }
                                                                                          }
                                                                                          break;
                                                                        case 2 ://y方向-1
                                                                              if(xp.y-1>=0 && !ROOM[xp.x][xp.y-1][xp.z]){
                                                                                          Point np(xp.x,xp.y-1,xp.z);
                                                                                          if(!np.equals(from)){
                                                                                              p.push(np);
                                                                                              ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
                                                                                              }
                                                                                          }
                                                                                          break;
                                                                        case 3 ://y方向+1
                                                                             if(xp.y+1<R && !ROOM[xp.x][xp.y+1][xp.z]){
                                                                                          Point np(xp.x,xp.y+1,xp.z);
                                                                                          if(!np.equals(from)){
                                                                                              p.push(np);
                                                                                              ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
                                                                                              }
                                                                                          }
                                                                                          break;
                                                                        case 4 ://z方向-1
                                                                             if(xp.z-1>=0 && !ROOM[xp.x][xp.y][xp.z-1]){
                                                                                          Point np(xp.x,xp.y,xp.z-1);
                                                                                          if(!np.equals(from)){
                                                                                              p.push(np);
                                                                                              ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
                                                                                              }
                                                                                          }
                                                                                          break;
                                                                        case 5 ://z方向+1
                                                                             if(xp.z+1<C && !ROOM[xp.x][xp.y][xp.z+1]){
                                                                                          Point np(xp.x,xp.y,xp.z+1);
                                                                                          if(!np.equals(from)){
                                                                                              p.push(np);
                                                                                              ROOM[np.x][np.y][np.z] = ROOM[xp.x][xp.y][xp.z]+1;
                                                                                              }
                                                                                          }
                                                                                          break;
                                                                        default :
                                                                                cout<<"Trapped!"<<endl;
                                                                                return;
                                                                        }
                                                                       
                                                              }
                                                      }   
                                           }
                                      cout<<"Trapped!"<<endl; 
                          }
     }

int main(){
    int L,R,C;
    cin>>L>>R>>C;
    while(L&&R&&C){
                          test(L,R,C);
                          cin>>L>>R>>C;
                   }
    return 0;
    }