#include <stdio.h>
#include <memory.h>
#include <queue>

using namespace std;

typedef struct state{
    int x,y,z;
    int step;

};

const int size = 105;

int visited[size][size][size];
int move[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int l,r,c;
state source,en;
queue <state> q;

int input(){
    int i,j,k;
    char ch;
    memset(visited,0,sizeof(visited));
    scanf("%d%d%d",&l,&r,&c);
    //printf("%d %d %d\n",l,r,c);
    while (!q.empty()) q.pop();
    if ( ( l == 0 ) && ( r == 0 ) && ( c == 0 ) ){
        return 0;
    }
    getchar();
    for ( k = 1; k <= l; k++ ){
        for ( i = 1; i <= r; i++ ){
            for ( j = 1; j <= c; j++ ){
                scanf("%c",&ch);
                if ( ch == '.' ) visited[i][j][k] = 0;
                if ( ch == 'E' ) {
                    en.x = i;
                    en.y = j;
                    en.z = k;
                    visited[i][j][k] = 0;
                }
                if ( ch == 'S' ) {
                    source.x = i;
                    source.y = j;
                    source.z = k;
                    source.step = 0;
                    visited[i][j][k] = 0;
                }
                if ( ch == '#' ) visited[i][j][k] = 1;
            }
            getchar();
        }
        getchar();
    }
    return 1;
}

int in( state v ){
    if ( ( v.x <= 0 ) || ( v.x > r ) ) return 0;
    if ( ( v.y <= 0 ) || ( v.y > c ) ) return 0;
    if ( ( v.z <= 0 ) || ( v.z > l ) ) return 0;
    return 1;
}


int BFS(){
    state s1,s2;
    int i;
    q.push(source);
    while ( !q.empty() ){
        s1 = q.front();
        //printf("%d %d %d\n",s1.x,s1.y,s1.z);
        //getchar();
        q.pop();
        if ( ( s1.x == en.x )&&( s1.y == en.y )&&( s1.z == en.z ) ) return s1.step;
        for ( i = 0; i <= 5; i++ ){
            s2.x = s1.x+move[i][0];
            s2.y = s1.y+move[i][1];
            s2.z = s1.z+move[i][2];
            if ( (in(s2) )&&( visited[s2.x][s2.y][s2.z] != 1 ) ){
                s2.step = s1.step+1;
                visited[s2.x][s2.y][s2.z] = 1;
                q.push(s2);
            }
        }
    }
    return -1;
}


void solve(){
    int ans;
    while ( input() ){
        ans = 0;
        ans = BFS();
        if ( ans == -1 ) printf("Trapped!\n");
            else printf("Escaped in %d minute(s).\n",ans);
    }
}

int main(){
    solve();
}

• Re:数组开到105才过的。。。太牛逼了这题。。。 (41) qoshi 2013-04-17 13:11:18
  • 多套测试数据，random出哪组就是哪组。。。一开始朴素bfs数组开到32过，后来双广开到40。。。幸好我没碰上105的。否则肯定又要耗很久。。 (2) openthedoor 2013-10-06 07:22:26
• ft！幸好我扩到40过了。。。要不然估计又要被搞很久了。。。 (0) openthedoor 2013-10-06 07:20:08