A - 王之迷宫

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/61

Description

王被困在了一个

Input

多组测试数据，对于每组测试数据，有三个整数 L,R,C（0<l,r,c≤30）。

L代表迷宫的高度，R和C分别代表每一层的行和列。

接下来是L个R×C的矩阵，矩阵包含4种字符（S,E,.,#）,S代表王的初始位置，E代表出口，#代表障碍。.代表能通过的地方。

每一层之后有一个空行。

当L=R=C=0时，输入中断。

Output

如果可以逃离迷宫，按下列格式输出最短时间：

Escaped in x minute(s). (x表示逃离迷宫的最短时间, 走一步花费一昏钟)

否则，输出:

Trapped!

Sample Input

3 4 5

S....

.###.

.##..

###.#

#####

##.##

##...

#####

#.###

####E

1 3 3

S##

#E#

###

0 0 0

Sample Output

Escaped in 11 minute(s).

Trapped!

HINT

题意

题解：

啊，3维bfs搞一搞就好了

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 200001#define mod 10007#define eps 1e-9int Num;char CH[20];//const int inf=0x7fffffff; //нчоч╢Сconst int inf=0x3f3f3f3f;/*inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}*///**************************************************************************************inline ll read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}string s[200][200];int vis[200][200][200];int dx[6]={ 0,0,1,-1,0,0};int dy[6]={ 1,-1,0,0,0,0};int dz[6]={ 0,0,0,0,1,-1};struct node{ int x,y,z; ll t;};int l,r,c;int main(){ while(scanf("%d%d%d",&l,&r,&c)!=EOF) { memset(vis,0,sizeof(vis)); if(l==0&&r==0&&c==0) break; node st,ed; for(int i=0;i
                   
                    >s[i][j]; for(int i=0;i
                    
                      q; q.push(st); while(!q.empty()) { node now=q.front(); q.pop(); if(s[now.x][now.y][now.z]=='E') { time=now.t; break; } for(int i=0;i<6;i++) { node next=now; next.x+=dx[i]; next.y+=dy[i]; next.z+=dz[i]; next.t++; if(next.x<0||next.x>=l) continue; if(next.y<0||next.y>=r) continue; if(next.z<0||next.z>=c) continue; if(s[next.x][next.y][next.z]=='#') continue; if(vis[next.x][next.y][next.z]) continue; vis[next.x][next.y][next.z]=1; q.push(next); } } if(time==-1) printf("Trapped!\n"); else printf("Escaped in %d minute(s).\n",time); }}