首页 > 代码库 > POJ 2251 Dungeon Master
POJ 2251 Dungeon Master
http://poj.org/problem?id=2251
这道题 就是3D版的迷宫问题
利用BFS求解即可 只需多加Z轴这一维度
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <queue> 5 #define READ() freopen("in.txt", "r", stdin); 6 7 using namespace std; 8 9 10 struct Loc 11 { 12 int l, r, c, step; 13 Loc () {} 14 Loc (int l, int r, int c, int step) : l(l), r(r), c(c), step(step) {} 15 }; 16 int L, R, C, sl, sr, sc; 17 char maze[32][32][32]; 18 bool use[32][32][32]; 19 20 21 int d[6][3] = 22 { 23 0, -1, 0, 24 0, 0, 1, 25 0, 1, 0, 26 0, 0, -1, 27 1, 0, 0, 28 -1, 0, 0 29 }; 30 bool OK(int l, int r, int c) 31 { 32 if (l < 0 || l >= L || r < 0 || r >= R || c < 0 || c >= C) return false; 33 if (maze[l][r][c] == ‘#‘) return false; 34 else return true; 35 } 36 int bfs() 37 { 38 queue<Loc> que; 39 Loc sloc = Loc(sl, sr, sc, 0); 40 que.push(sloc); 41 while (!que.empty()) 42 { 43 Loc loc = que.front(); 44 que.pop(); 45 if (use[loc.l][loc.r][loc.c]) continue; 46 use[loc.l][loc.r][loc.c] = true; 47 for (int i = 0; i < 6; i++) 48 { 49 int nl = loc.l + d[i][0], nr = loc.r + d[i][1], nc = loc.c + d[i][2]; 50 if (OK(nl, nr, nc)) 51 { 52 if (maze[nl][nr][nc] == ‘E‘) return loc.step+1; 53 else if (!use[nl][nr][nc]); 54 { 55 Loc nloc = Loc(nl, nr, nc, loc.step+1); 56 que.push(nloc); 57 } 58 } 59 } 60 } 61 return -1; 62 } 63 64 int main() 65 { 66 //READ() 67 while (~scanf("%d%d%d", &L, &R, &C)) 68 { 69 if (L == 0 && R == 0 && C == 0) break; 70 getchar(); 71 for (int l = 0; l < L; l++) 72 { 73 for (int r = 0; r < R; r++) 74 { 75 for (int c = 0; c < C; c++) 76 { 77 scanf("%c", &maze[l][r][c]); 78 if (maze[l][r][c] == ‘S‘) 79 { 80 sl = l; 81 sr = r; 82 sc = c; 83 } 84 } 85 getchar(); 86 } 87 getchar(); 88 } 89 memset(use, 0, sizeof(use)); 90 int ans = bfs(); 91 if ( ans == -1) puts("Trapped!"); 92 else printf("Escaped in %d minute(s).\n", ans); 93 } 94 }
POJ 2251 Dungeon Master
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。