UVA532Dungeon Master

UVA-532

题意:给出一个有L层,每层为R×C的三位空间,S为初始位置,E为出口,求S到E的最短时间 。
解题思路:= =。三维上的bfs,其实和矩阵上的bfs没什么差别,把每层的矩阵读进来,bfs一下就好了。

/*************************************************************************
     File Name: UVA-532.cpp
     Author: Narsh
     
     Created Time: 2016年07月20日 星期三 18时41分57秒
 ************************************************************************/

#include iostream
#include algorithm
#include cstdio
#include cstring
using namespace std;
struct node{
    int x,y,z,time;
}q[600000];
bool pd[31][32][32];
const int c[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int h,m,n,k,t,H;
int endx,endy,endz;
string s[60][32];
int main() {
    while (scanf("%d%d%d",h,n,m)  n+m+h) {
        H=t=0;
        memset(pd,false,sizeof(pd));
        for (int k = 1; k = h; k++)
            for (int i = 1; i = n; i++) {
                cins[k][i];
                s[k][i]=" "+s[k][i];
                for (int j = 1; j = m; j++) {
                    if (s[k][i][j] == 'S') {
                        t++;
                        q[t].x=i;
                        q[t].y=j;
                        q[t].z=k;
                        q[t].time=0;
                        pd[i][j][k]=false;
                    }
                    if (s[k][i][j] == 'E') {
                        endx=i;
                        endy=j;
                        endz=k;
                        s[k][i][j] = '.';
                    }
                    if (s[k][i][j] == '.') 
                        pd[i][j][k]=true;
                }
            }
        int x,y,z;
        while (H = t) {
            H++;
            if (endx == q[H].x  endy == q[H].y  endz == q[H].z){
                printf("Escaped in %d minute(s).\n",q[H].time);
                break;
            }
            for (int i = 0; i  6; i++){
                x=q[H].x+c[i][0];
                y=q[H].y+c[i][1];
                z=q[H].z+c[i][2];
                if (pd[x][y][z]  s[z][x][y] == '.') {
                    pd[x][y][z]=false;
                    t++;
                    q[t].x=x;
                    q[t].y=y;
                    q[t].z=z;
                    q[t].time = q[H].time+1;
                }
            }
        }
        if (H  t) printf("Trapped!\n");
    }
}
最新回复(0)
/jishu2RRM6mQWK6vx8sHFACxYysZEch5J_2Bffo1C7tuA_3D_3D4795036
8 简首页