习惯用双广了，这次WA了好几次，标记起和终止始节点时发现了错误，后来没改彻底，具体见注释行。
双广速度快，空间小，结构也相对 bfs 简单；
# include <stdio.h> # include <string.h> typedef struct {char l, r, c;}Pos; /* char 足够了，比较时没出错 */ const int dir[][3] = {{0,0,1}, {0,0,-1}, {0,1,0}, {0,-1,0}, {1,0,0}, {-1,0,0}}; Pos start, goal; char L, R, C; char dun[35][35][35]; char vis[35][35][35]; short dis[35][35][35]; char read_data(void) { char f1, f2; int i, j, k; if (~scanf("%d%d%d", &L, &R, &C)) return 0; if (L==0 && R==0 && C==0) return 0; f1 = f2 = 1; for (i = 1; i <= L; ++i) for (j = 1; j <= R; ++j) { scanf("%s", dun[i][j]+1); for (k = 1; f1 && k<=C; ++k) if (dun[i][j][k] == 'S') { f1 = 0; start.l = i; /* WA: start.l = 1 */ start.r = j; start.c = k; break; } for (k = 1; f2 && k<=C; ++k) if (dun[i][j][k] == 'E') { f2 = 0; goal.l = i; /* WA: goal.l = L */ goal.r = j; goal.c = k; break; } } return 1; } int bfs(void) { Pos Q[30000], cur, nst; char nl, nr, nc; int front, rear, i; memset(vis, 0, sizeof(vis)); /* WA vis必须要清空，dis则不是必须的 */ front = 1; rear = 3; Q[1] = start; Q[2] = goal; vis[start.l][start.r][start.c] = 1; vis[ goal.l][ goal.r][ goal.c] = 2; dis[start.l][start.r][start.c] = 0; dis[ goal.l][ goal.r][ goal.c] = 0; while (front < rear) { cur = Q[front++]; for (i = 0; i < 6; ++i) { nl = cur.l + dir[i][0]; nr = cur.r + dir[i][1]; nc = cur.c + dir[i][2]; if (1<=nl&&nl<=L && 1<=nr&&nr<=R && 1<=nc&&nc<=C && dun[nl][nr][nc]!='#') { if (!vis[nl][nr][nc]) { nst.l = nl, nst.r = nr, nst.c = nc; Q[rear++] = nst; vis[nl][nr][nc] = vis[cur.l][cur.r][cur.c]; dis[nl][nr][nc] = dis[cur.l][cur.r][cur.c] + 1; } else if (vis[cur.l][cur.r][cur.c] != vis[nl][nr][nc]) { return dis[cur.l][cur.r][cur.c] + dis[nl][nr][nc] + 1; } } } } return -1; } void solve(void) { int ans; ans = bfs(); if (ans == -1) puts("Trapped!"); else printf("Escaped in %d minute(s).\n", ans); } int main() { while (read_data()) { solve(); } return 0; }
.