BFS
C++ 代码
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// (level, x, y)
using P = tuple<int, int, int>;
static constexpr int dirs[][3] {{0, -1, 0}, {-1, 0, 0}, {0, 1, 0}, {1, 0, 0}, {0, 0, -1}, {0, 0, 1}};
int L, R, C, sl, sx, sy; // l == level (层数)
string s;
int bfs(vector<vector<vector<char>>>& g, int sl, int sx, int sy) {
queue<P> q;
q.emplace(sl, sx, sy);
g[sl][sy][sx] = '#'; // mark as seen
int steps = 0;
while (not q.empty()) {
size_t sz = q.size();
while (sz--) {
const auto [l, x, y] = q.front(); q.pop();
for (const auto& d : dirs) {
int nl = l + d[2], nx = x + d[0], ny = y + d[1];
if (nl < 0 || nx < 0 || ny < 0 || nl == L || nx == C || ny == R || g[nl][ny][nx] == '#')
continue;
if (g[nl][ny][nx] == 'E') return steps + 1;
q.emplace(nl, nx, ny);
g[nl][ny][nx] = '#'; // mark as seen
}
}
++steps;
}
return -1;
}
int main(void) {
while (scanf("%d %d %d", &L, &R, &C) && L) {
vector<vector<vector<char>>> g(L, vector<vector<char>>(R, vector<char>(C))); // 三维地牢
for (int l = 0; l < L; ++l)
for (int y = 0; y < R; ++y) {
cin >> s;
for (int x = 0; x < C; ++x) {
g[l][y][x] = s[x];
if (g[l][y][x] == 'S') sl = l, sx = x, sy = y;
}
}
int ans = bfs(g, sl, sx, sy);
cout << (ans >= 0 ? "Escaped in " + to_string(ans) + " minute(s)." : "Trapped!") << endl;
}
}
C 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <stdbool.h>
#define N 110
#define fast_read() r()
typedef long long int ll;
typedef enum { OK = 1, ERROR = -1, OVERFLOW = -2 } Status;
typedef struct {
int x, y, z;
} Coord;
// ================== 循环队列的数据结构与存储表示 ==================
typedef Coord QElemType;
typedef struct {
QElemType* base;
int front;
int rear;
size_t capacity;
} SqQueue;
Status InitQueue(SqQueue* Q, int capacity) {
if (!(Q->base = (QElemType*) malloc((capacity + 1) * sizeof(QElemType)))) {
// may be no enough space!
fprintf(stdout, "InitQueue Memory Overflow: %s", strerror(errno));
exit(OVERFLOW);
}
Q->front = Q->rear = 0;
Q->capacity = capacity + 1;
return OK;
}
bool QueueEmpty(SqQueue* Q) {
return Q->front == Q->rear;
}
bool QueueFull(SqQueue* Q) {
return (Q->rear + 1) % Q->capacity == Q->front;
}
size_t QueueLength(SqQueue* Q) {
// 公式好像是这么背的!
return (Q->rear - Q->front + Q->capacity) % Q->capacity;
}
Status EnQueue(SqQueue* Q, QElemType e) {
if (QueueFull(Q)) {
fprintf(stdout, "EnQueue ERROR: The Queue is full!\n");
return ERROR;
}
*(Q->base + Q->rear) = e;
Q->rear = (Q->rear + 1) % Q->capacity;
return OK;
}
Status DeQueue(SqQueue* Q, QElemType* e) {
if (QueueEmpty(Q)) {
fprintf(stdout, "DeQueue ERROR: The Queue is empty!\n");
return ERROR;
}
*e = *(Q->base + Q->front);
Q->front = (Q->front + 1) % Q->capacity;
return OK;
}
Status DestroyQueue(SqQueue *Q) {
free(Q->base);
return OK;
}
// ================== 循环队列的数据结构与存储表示 ==================
ll fast_read() {
ll n = 0, sign = 1;
char c = getchar();
while (c < 48 || c > 57) {
if (c == '-') sign = -1;
c = getchar();
}
while (c >= 48 && c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
char grid[N][N][N]; // 三维地牢
int bfs(const int l, const int m, const int n, int sl, int sx, int sy) {
SqQueue Q;
InitQueue(&Q, 1E5);
EnQueue(&Q, (Coord) {.z = sl, .x = sx, .y = sy});
grid[sl][sy][sx] = '#'; // mark as visited
// 三维坐标,6个方向 (上,左,下,右,下楼, 上楼)
const int dirs[][3] = {{0, 0, -1}, {0, -1, 0}, {0, 0, 1},
{0, 1, 0}, {1, 0, 0}, {-1, 0, 0}};
Coord coord;
int steps = 0, x, y, z, nx, ny, nz;
while (!QueueEmpty(&Q)) {
size_t s = QueueLength(&Q);
while (s--) {
DeQueue(&Q, &coord);
x = coord.x, y = coord.y, z = coord.z;
for (int i = 0; i < 6; ++i) {
nz = z + dirs[i][0], nx = x + dirs[i][1], ny = y + dirs[i][2];
if (nz < 0 || nz == l || nx < 0 || nx == n || ny < 0 || ny == m
|| grid[nz][ny][nx] == '#')
continue;
if (grid[nz][ny][nx] == 'E')
return DestroyQueue(&Q), steps + 1;
EnQueue(&Q, (Coord) {.z = nz, .x = nx, .y = ny});
grid[nz][ny][nx] = '#';
}
}
++steps;
}
DestroyQueue(&Q);
return -1;
}
int main(int argc, char const *argv[]) {
int l, m, n;
while (scanf("%d %d %d ", &l, &m, &n), l) {
int x, y, z, sl, sx, sy;
for (z = 0; z < l; ++z) {
for (y = 0; y < m; ++y) {
for (x = 0; x < n; ++x) {
scanf("%c", &grid[z][y][x]);
if (*(*(*(grid + z) + y) + x) == 'S')
sl = z, sx = x, sy = y;
}
getchar();
}
getchar();
}
int ans = bfs(l, m, n, sl, sx, sy);
if (ans == -1) puts("Trapped!");
else printf("Escaped in %d minute(s).\n", ans);
}
return 0;
}