532 - Dungeon Master（bfs）

本文主要是介绍532 - Dungeon Master（bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：532 - Dungeon Master

题目大意：三维的迷宫。

解题思路：BFS。和前面一题二维的一样，就是改成三维的。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;const int N = 35;
int l, r, c;struct dungeon{char s[N][N];}d[N];int dir[6][3] = {{-1, 0, 0}, {0, -1, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {0, 0, -1}};struct VISIT {int s[N][N];}visit[N], path[N];struct addr {int x, y, z;
} e;queue<addr> q;void bfs(addr s1) {visit[s1.z].s[s1.x][s1.y] = 1;if(s1.x == e.x && s1.y == e.y && s1.z == e.z)return ;q.push(s1);while(!q.empty()) {s1 = q.front();q.pop();for(int i = 0; i < 6; i++) {int x = s1.x + dir[i][0];int y = s1.y + dir[i][1];int z = s1.z + dir[i][2];if( x >= 0 && x < r  && y >= 0 && y < c && z >= 0 && z < l) {if(d[z].s[x][y] != '#' && !visit[z].s[x][y]) {visit[z].s[x][y] = 1;path[z].s[x][y] = path[s1.z].s[s1.x][s1.y] + 1;if(x == e.x && y == e.y && z == e.z)return ;addr s2;s2.x = x; s2.y = y; s2.z = z;q.push(s2);}}}}}int main() {while(scanf("%d%d%d", &l, &r, &c) , l || r || c) {int i, j, k;addr a;memset(d, 0, sizeof(d));memset(visit, 0, sizeof(visit));memset(path, 0, sizeof(path));for( i = 0; i < l; i++) for( j = 0; j < r; j++)scanf("%s", d[i].s[j]);for(i = 0; i < l; i++)for(j = 0; j < r; j++)for(k = 0; k < c; k++) {if(d[i].s[j][k] == 'S') {a.x = j;a.y = k;a.z = i;}if(d[i].s[j][k] == 'E'){e.x = j;e.y = k;e.z = i;}}bfs(a);if(visit[e.z].s[e.x][e.y]) printf("Escaped in %d minute(s).\n", path[e.z].s[e.x][e.y]);elseprintf("Trapped!\n");while(!q.empty()) {q.pop();}} return 0;
}

这篇关于532 - Dungeon Master（bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---