poj bfs与dfs总结之2251 Dungeon Master 这道题我最开始用的是dfs，结果发现超时，看了大神总结的以及我的上一个博客。 总结： 1、如果是求最短路径，树的直径（两次bfs），一般用bfs 2、如果只是左转或者右转（像上一篇博客一样的话）就用dfs 3、如果是翻转系列的（flip game，行列变换）一定是dfs
超时的：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<algorithm> #include<queue> #define INF 10020 using namespace std; char tmp[40]; int L, R, C, S[3], E[3], ans, mark[35][35][35], Path[35][35][35]; int Dir[6][3] = { { -1, 0, 0 }, { 1, 0, 0 }, { 0, -1, 0 }, { 0, 1, 0 }, { 0, 0, -1 }, { 0, 0, 1 } }; void dfs(int x, int y, int z,int dep) { if (x == E[0] && y == E[1] && z == E[2]) { ans = min(ans, dep); return; } int a, b, c, i, j, k; for (i = 0; i < 6; i++) { a = x + Dir[i][0]; b = y + Dir[i][1]; c = z + Dir[i][2]; if (a >= 0 && a < L&&b >= 0 && b < R&&c >= 0 && c < C) { if (Path[a][b][c] && !mark[a][b][c]) { mark[a][b][c] = 1; dfs(a, b, c, dep + 1); mark[a][b][c] = 0; } } } } int main() { freopen("1.txt", "r", stdin); int i, j, k, t,u,v, cases; while (scanf("%d%d%d", &L, &R, &C) != EOF && (L || R || C)) { memset(Path, 0, sizeof(Path)); memset(mark, 0, sizeof(mark)); for (i = 0; i < L; i++) for (j = 0; j < R; j++) { scanf("%s", tmp); for (k = 0; k < C; k++) { if (tmp[k] == '.') { Path[i][j][k] = 1; } else if (tmp[k] == 'S') { Path[i][j][k] = 1; S[0] = i; S[1] = j; S[2] = k; } else if (tmp[k] == 'E') { Path[i][j][k] = 1; E[0] = i; E[1] = j; E[2] = k; } } } ans = INF; mark[S[0]][S[1]][S[2]] = 1; dfs(S[0], S[1], S[2], 0); if (ans >= INF) { printf("Trapped!\n"); } else { printf("Escaped in %d minute(s).\n", ans); } } return 0; }正确的bfs版本：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<algorithm> #include<queue> #define INF 10020 using namespace std; char tmp[40]; int L, R, C, S[3], E[3], ans, mark[35][35][35], Path[35][35][35]; int Dir[6][3] = { { -1, 0, 0 }, { 1, 0, 0 }, { 0, -1, 0 }, { 0, 1, 0 }, { 0, 0, -1 }, { 0, 0, 1 } }; struct Point { int x, y, z; }; void bfs(int x, int y, int z) { queue<Point> que; int a, b, c, i, j, k, t, count; bool flag = 0; Point tmp; tmp.x = x; tmp.y = y; tmp.z = z; que.push(tmp); count = 0; while (!que.empty()) { count++; t = que.size(); while (t > 0) { Point cur = que.front(); que.pop(); if (cur.x == E[0] && cur.y == E[1] && cur.z == E[2]) { ans = count - 1; flag = 1; break; } for (i = 0; i < 6; i++) { a = cur.x + Dir[i][0]; b = cur.y + Dir[i][1]; c = cur.z + Dir[i][2]; if (a >= 0 && a < L&&b >= 0 && b < R&&c >= 0 && c < C) { if (Path[a][b][c] && !mark[a][b][c]) { mark[a][b][c] = 1; Point tmp; tmp.x = a; tmp.y = b; tmp.z = c; que.push(tmp); } } } t--; } if (flag) break; } } int main() { freopen("1.txt", "r", stdin); int i, j, k, t,u,v, cases; while (scanf("%d%d%d", &L, &R, &C) != EOF && (L || R || C)) { memset(Path, 0, sizeof(Path)); memset(mark, 0, sizeof(mark)); for (i = 0; i < L; i++) for (j = 0; j < R; j++) { scanf("%s", tmp); for (k = 0; k < C; k++) { if (tmp[k] == '.') { Path[i][j][k] = 1; } else if (tmp[k] == 'S') { Path[i][j][k] = 1; S[0] = i; S[1] = j; S[2] = k; } else if (tmp[k] == 'E') { Path[i][j][k] = 1; E[0] = i; E[1] = j; E[2] = k; } } } ans = INF; mark[S[0]][S[1]][S[2]] = 1; bfs(S[0], S[1], S[2]); if (ans >= INF) { printf("Trapped!\n"); } else { printf("Escaped in %d minute(s).\n", ans); } } return 0; }