POJ-2251 Dungeon Master

POJ-2251 Dungeon Master

题目链接：POJ-2251


题目大意：三维迷宫最短路径

解题思路：就是bfs 然后6个方向 注意走过的点变墙就行了

#include<iostream>
#include<queue>

using namespace std;

char arrA[35][35][35]={'\0'};
int l,r,c;
int sum = 0;
int xxx[6]={0,0,1,0,0,-1};
int yyy[6]={0,1,0,0,-1,0};
int zzz[6]={1,0,0,-1,0,0};
bool isU = false; 
void bfs(int x, int y, int z);

typedef struct myNode{
    int x;
    int y;
    int z;
    int step;
} node;

int main(){
    while(cin>>l>>r>>c){
        if(l + r + c == 0) return 0;
        int beginX, beginY, beginZ;
        for(int i = 1; i <= l; i++){
            for(int j = 1; j <= r; j++){
                for(int k = 1; k <= c; k++){
                    cin>>arrA[i][j][k];
                    if(arrA[i][j][k] == 'S'){
                        beginX = i;
                        beginY = j;
                        beginZ = k;
                    }
                }
            }
        }
        arrA[beginX][beginY][beginZ] = '#'; 
        bfs(beginX, beginY, beginZ);
        if(isU)cout<<"Escaped in "<<sum<<" minute(s)."<<endl;
        else cout<<"Trapped!"<<endl;
        sum = 0;
        isU = false; 
    }
    return 0;
}
void bfs(int x, int y, int z){
    queue<node> queueA;
    node n1;
    n1.x = x;
    n1.y = y;
    n1.z = z;
    n1.step = 0;
    queueA.push(n1);
    while(queueA.size()){
        if(arrA[queueA.front().x][queueA.front().y][queueA.front().z] == 'E'){
            sum = queueA.front().step;
            isU = true;
            break;
        }
        sum++;
        for(int i = 0; i < 6; i++){
            int xx = queueA.front().x + xxx[i];
            int yy = queueA.front().y + yyy[i];
            int zz = queueA.front().z + zzz[i];
            if(xx >= 1 && xx <= l && yy >= 1 && yy <= r && zz >= 1 && zz <= c && arrA[xx][yy][zz] != '#'){
                if(arrA[xx][yy][zz] == '.') arrA[xx][yy][zz] = '#';
                n1.x = xx;
                n1.y = yy;
                n1.z = zz;
                n1.step = queueA.front().step + 1;
                queueA.push(n1);
            }
        } 
        queueA.pop(); 
    }
}