• Dungeon Master


    原题链接

    题解

    一个三维的bfs,直接向6个方向走就是了,直接套模板

    #include <iostream>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    typedef struct node{
        int x, y, z;
        node(int a, int b, int c){
            x = a, y = b, z = c;
        }
    };
    
    int dx[6]={1,-1,0,0,0,0}, dy[6]={0,0,1,-1,0,0},dz[6]={0,0,0,0,1,-1};
    char g[32][32][32];
    int st[32][32][32];
    
    int l,r,c;
    
    int main(){
    
        while(cin >> l >> r >> c){
            int x, y, z;
            int ex, ey, ez;
            if(l == 0 && r == 0 && c == 0) break;
    
            for(int i = 0; i < l; ++i){
                for(int j = 0; j < r; ++j){
                    for(int k = 0; k < c; ++k){
                        cin >> g[i][j][k];
                        if(g[i][j][k] == 'S') x = i, y = j, z = k;
                        if(g[i][j][k] == 'E') ex = i, ey = j, ez = k;
                        st[i][j][k] = -1;
                    }
                }
            }
    
            queue<node> q;
            q.push(node(x, y, z)); st[x][y][z] = 0;
    
            while(q.size()){
                node t = q.front(); q.pop();
                //感觉这条语句放进下面中要更好,直接找到了就直接退出
                if(t.x == ex && t.y == ey && t.z == ez) break;//表示的终点在队列中,所以下面的判定中当点为终点是也要把点加进来
                for(int i = 0; i < 6; ++i){
                    x = t.x + dx[i];
                    y = t.y + dy[i];
                    z = t.z + dz[i];
                    if(x >= 0 && x < l && y >= 0 && y < r && z >= 0 && z < c && (g[x][y][z] == '.' || g[x][y][z] == 'E') && st[x][y][z] == -1){
                        q.push(node(x, y, z));
                        st[x][y][z] = st[t.x][t.y][t.z] + 1;
                    }
                }
            }
    
            if(st[ex][ey][ez] == -1) cout << "Trapped!" << endl;
            else cout << "Escaped in "<< st[ex][ey][ez] << " minute(s)." << endl;
        }        
        return 0;
    }
    

    这个POJ提交题目是真的恶心,支持的版本的C++太低了,搞得人难受的一批

  • 相关阅读:
    Templet
    linux command
    Codeforces Daily
    Programming Contest Challenge Book
    STL
    Struct
    Some of GDUFE
    [屯题] DP系列
    [颓废]ws_fqk省选前刷题记录
    [SDOI2009][BZOJ1876] SuperGCD|高精度|更相减损术
  • 原文地址:https://www.cnblogs.com/Lngstart/p/13234884.html
一二三 - 开发者的网上家园