POJ 2251 B - Dungeon Master——双广度优先搜索

POJ 2251 B - Dungeon Master——双广度优先搜索

题意：在一个三维空间中寻找起止点之间的最短路，每次可以朝着同一个平面的前后左右走，或者到上一个平面或下一个平面与当前平面相同的位置。

思路：bfs暴一遍超时，考虑双向bfs

#include #include #include #include #include using namespace std;const int dx[] = {0, 0, -1, 1};const int dy[] = {1, -1, 0, 0};int l, r, c, ans, vis[50][50][50], visr[50][50][50];struct Graph{ char g[50][50];}G[50];struct Point{ int x, y, z;}st, ed;struct State{ int x, y,z, step;}state, temp;void bfs(){ ans = -1; memset(vis, 0, sizeof(vis)); memset(visr, 0, sizeof(visr)); queue q; queue qr; state.x = st.x, state.y = st.y, state.z = st.z, state.step = 0; vis[st.x][st.y][st.z] = 1; q.push(state); state.x = ed.x, state.y = ed.y, state.z = ed.z, state.step = 0; visr[ed.x][ed.y][ed.z] = 1; qr.push(state); int STEP = 0, STEPR = 0; while (!q.empty() || !qr.empty()) { while (!q.empty() && q.front().step <= STEP) { temp = q.front(); q.pop(); int x = temp.x, y = temp.y, z = temp.z, step = temp.step; int STEP = step; if (visr[x][y][z]) { ans = STEP + STEPR; return; } for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (0 <= xx && xx < r && 0 <= yy && yy < c && !vis[xx][yy][z] && G[z].g[xx][yy] != '#') { vis[xx][yy][z] = 1; state.x = xx, state.y = yy, state.z = z, state.step = step + 1; q.push(state); } } if (z + 1 < l && !vis[x][y][z + 1] && G[z + 1].g[x][y] != '#') { vis[x][y][z + 1] = 1; state.x = x, state.y = y, state.z = z + 1; state.step = step + 1; q.push(state); } if (z - 1 >= 0 && !vis[x][y][z - 1] && G[z - 1].g[x][y] != '#') { vis[x][y][z - 1] = 1; state.x = x, state.y = y, state.z = z - 1; state.step = step + 1; q.push(state); } } if (!q.empty()) STEP++; /*---------------------------------------------------------------*/ while (!qr.empty() && qr.front().step <= STEPR) { temp = qr.front(); qr.pop(); int x = temp.x, y = temp.y, z = temp.z, step = temp.step; if (vis[x][y][z]) { ans = STEP + STEPR; return; } for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (0 <= xx && xx < r && 0 <= yy && yy < c && !visr[xx][yy][z] && G[z].g[xx][yy] != '#') { visr[xx][yy][z] = 1; state.x = xx, state.y = yy, state.z = z, state.step = step + 1; qr.push(state); } } if (z + 1 < l && !visr[x][y][z + 1] && G[z + 1].g[x][y] != '#') { visr[x][y][z + 1] = 1; state.x = x, state.y = y, state.z = z + 1; state.step = step + 1; qr.push(state); } if (z - 1 >= 0 && !visr[x][y][z - 1] && G[z - 1].g[x][y] != '#') { visr[x][y][z - 1] = 1; state.x = x, state.y = y, state.z = z - 1; state.step = step + 1; qr.push(state); } } if (!qr.empty()) STEPR++; }}int main(){ while (scanf("%d %d %d", &l, &r, &c) == 3 && (l + r + c)) { for (int i = 0; i < l; i++) { getchar(); for (int j = 0; j < r; j++) { for (int k = 0; k < c; k++) { G[i].g[j][k] = getchar(); if (G[i].g[j][k] == 'S') { st.z = i, st.x = j, st.y = k; } else if (G[i].g[j][k] == 'E') { ed.z = i, ed.x = j, ed.y = k; } } getchar(); } } bfs(); if (ans == -1) { printf("Trapped!\n"); } else { printf("Escaped in %d minute(s).\n", ans); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。