POJ.2251 Dungeon Master （三维BFS）

题意分析

你被困在一个3D地牢中且继续寻找最短路径逃生。地牢由立方体单位构成，立方体中不定会充满岩石。向上下前后左右移动一个单位需要一分钟。你不能对角线移动并且迷宫四周坚石环绕。

若能逃离，则输出逃离需要的最短时间，否则输出Trapped!。

与二维BFS的差别在于，多了一个上下两层。所以除了先后左右移动，还要有上下移动，对于每个位置，总共有6种移动方式，将6种移动方式种可行的每次塞进队列里面就好了。

依旧还要记录歩数。此题没什么大坑。

代码总览

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#define nmax 30

using namespace std;

char mp[nmax][nmax][nmax];

bool visit[nmax][nmax][nmax];

int Slevel,Sx,Sy,Elevel,Ex,Ey;

int spx[4] = {0,1,0,-1};

int spy[4] = {1,0,-1,0};

int spl[2] = {-1,1};

bool isout = false;

int l,r,c,ans;

typedef struct mes{

    int level;

    int x;

    int y;

    int steps;

}mes;

void changeVisit(mes temp)

{

    visit[temp.level][temp.x][temp.y]  =  true;

    return;

}

bool check(mes temp)

{

    if(temp.level >= l || temp.level <0 || temp.x <0 || temp.x>=r || temp.y<0 || temp.y>=c || visit[temp.level][temp.x][temp.y] || mp[temp.level][temp.x][temp.y] == '#')

        return false;

    return true;

}

void bfs()

{

    queue<mes> q;

    while(!q.empty()) q.pop();

    mes sta = {Slevel,Sx,Sy,0},temp,head;

    q.push(sta);

    changeVisit(sta);

    while(!q.empty()){

        head = q.front();q.pop();

        if(head.level == Elevel && head.x == Ex && head.y == Ey){

            isout = true;

            ans = head.steps;

            break;

        }

        for(int i = 0;i<4;++i){

            temp.level = head.level;

            temp.x = head.x + spx[i];

            temp.y = head.y + spy[i];

            temp.steps = head.steps + 1;

            if(check(temp)){

                q.push(temp);

                changeVisit(temp);

            }

        }

        for(int i = 0;i<2;++i){

            temp.level = head.level + spl[i];

            temp.x = head.x;

            temp.y = head.y;

            temp.steps = head.steps + 1;

            if(check(temp)){

                q.push(temp);

                changeVisit(temp);

            }

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%d %d %d",&l,&r,&c) != EOF){

        if( l == 0 && r == 0 && c == 0) break;

        isout = false;

        memset(mp,0,sizeof(mp));

        memset(visit,0,sizeof(mp));

        for(int i = 0;i<l;++i){

            for(int j = 0;j<r;++j){

                scanf("%s",mp[i][j]);

                for(int k = 0;k<c;++k){

                    if(mp[i][j][k] == 'S'){

                        Slevel = i; Sx = j; Sy = k;

                    }else if(mp[i][j][k] == 'E'){

                        Elevel = i; Ex = j; Ey = k;

                    }

                }

            }

        }

        bfs();

        if(isout == true){

            printf("Escaped in %d minute(s).\n",ans);

        }else{

            printf("Trapped!\n");

        }

    }

    return 0;

}