POJ2251 Dungeon Master（BFS）

4 years ago

source link: https://arminli.com/poj2251/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

POJ2251 Dungeon Master（BFS）

January 15, 2016

题目链接

题意：三维的图，可以上下东南西北的走，所以方向是 6 个。在同坐标的不同 level 可以通过上下到达。每步时间是 1，问从 S 到 E 的最短时间。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;

int dir[6][3]={-1,0,0,
                1,0,0,
                0,-1,0,
                0,1,0,
                0,0,-1,
                0,0,1};
int l, r, c, ans;
char pic[35][35][35];
int flag[35][35][35];
struct point{
    int x, y, z;
    int n;
};
bool judge(int x, int y, int z){
    if(x >= 0 && x <l && y >= 0 && y <r && z >= 0 && z < c)
        return 1;
    else return 0;
}

void bfs(int x, int y, int z){
    queue<point> q;
    point p0, p1, p2;
    p0.x = x; p0.y = y; p0.z = z; p0.n = 0;
    flag[x][y][z] = 1;
    q.push(p0);
    while(!q.empty()){
        p1 = q.front();
        q.pop();
        for(int i = 0; i < 6; i++){
            int x1 = p1.x + dir[i][0];
			int y1 = p1.y + dir[i][1];
			int z1 = p1.z + dir[i][2];
			if(judge(x1, y1, z1) && !flag[x1][y1][z1] && pic[x1][y1][z1] != '#'){
				if(pic[x1][y1][z1] == 'E'){
					ans = p1.n + 1;
					return;
				}
				p2.x = x1;
				p2.y = y1;
				p2.z = z1;
				p2.n = p1.n+1;
				flag[x1][y1][z1] = 1;
				q.push(p2);
			}
        }
    }
}

int main(){
    //freopen("a.txt", "r", stdin);
    int si, sj, sk;
    while(scanf("%d %d %d", &l, &r, &c) != EOF){
        if(!l && !r && !c) break;
        memset(flag, 0, sizeof(flag));
        for(int i = 0; i < l; i++){
            for(int j = 0; j < r; j++){
                scanf("%s", pic[i][j]);
                for(int k = 0; k < c; k++)
                    if(pic[i][j][k] == 'S'){
                        si = i; sj = j; sk = k;
                    }
            }
        }
        ans = -1;
        bfs(si, sj, sk);
        if(ans != -1)
		    printf("Escaped in %d minute(s).n", ans);
		else
		    printf("Trapped!n");
    }
    return 0;
}

Recommend