优化这段代码 #include <bits/stdc++.h> using namespace std; int n, m, l; char s[110][110][110]; int ux, uy, uz; bool vis[110][110][110]; int dx[] = {1, -1, 0, 0, 0, 0}, dy[] = {0, 0, 1, -1, 0, 0}, dz[] = {0, 0, 0, 0, 1, -1}; struct node { int x, y, z, d; node(int _x = 0, int _y = 0, int _z = 0, int _d = 0): x(_x), y(_y), z(_z), d(_d){} }; void bfs() { queue<node> q; q.push(node(ux, uy, uz, 0)); while (!q.empty()) { node t = q.front(); q.pop(); int x = t.x, y = t.y, z = t.z, d = t.d; vis[x][y][z] = true; s[x][y][z] = '#'; for (int i = 0; i < 6; i++) { int kx = x + dx[i], ky = y + dy[i], kz = z + dz[i]; if (kx < 0 || kx >= n || ky < 0 || ky >= m || kz < 0 || kz >= l || vis[kx][ky][kz] || s[kx][ky][kz] == '#') continue; if (s[kx][ky][kz] == 'E') { printf("Escaped in %d minute(s).\n", d + 1); return; } q.push(node(kx, ky, kz, d + 1)); } } printf("Trapped!\n"); } int main() { while (scanf("%d%d%d", &n, &m, &l) == 3) { if (n == 0 && m == 0 && l == 0) break; for (int i = 0; i < n; i++) for (int j = 0; j < m;j++) scanf("%s", &s[i][j]); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < l; k++) if (s[i][j][k] == 'S') ux = i, uy = j, uz = k; bfs(); } return 0; }
时间: 2024-03-25 08:37:55 浏览: 76
这段代码的优化可以从以下几个方面入手:
1. 使用 memset 初始化访问数组和距离数组,以免产生垃圾值影响程序运行。
2. 在 BFS 遍历时,可以使用双向 BFS(即从起点和终点同时开始 BFS),以减少遍历的节点数,提高程序效率。
3. 在输入迷宫地图时,可以使用 fgets 函数读入一整行,然后使用 sscanf 函数解析出每个字符,以提高输入效率。
下面是代码的优化版:
```c++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
char s[MAXN][MAXN][MAXN];
int n, m, l, ux, uy, uz;
bool vis[MAXN][MAXN][MAXN];
int dx[] = {1, -1, 0, 0, 0, 0}, dy[] = {0, 0, 1, -1, 0, 0}, dz[] = {0, 0, 0, 0, 1, -1};
struct node {
int x, y, z, d;
node(int _x = 0, int _y = 0, int _z = 0, int _d = 0): x(_x), y(_y), z(_z), d(_d){}
};
void bfs(queue<node>& q, bool vis[][MAXN][MAXN]) {
node t = q.front();
q.pop();
int x = t.x, y = t.y, z = t.z, d = t.d;
vis[x][y][z] = true;
s[x][y][z] = '#';
for (int i = 0; i < 6; i++) {
int kx = x + dx[i], ky = y + dy[i], kz = z + dz[i];
if (kx < 0 || kx >= n || ky < 0 || ky >= m || kz < 0 || kz >= l || vis[kx][ky][kz] || s[kx][ky][kz] == '#') continue;
if (s[kx][ky][kz] == 'E') {
printf("Escaped in %d minute(s).\n", d + 1);
return;
}
q.push(node(kx, ky, kz, d + 1));
}
}
int bidirectional_bfs() {
queue<node> q1, q2;
memset(vis, false, sizeof(vis));
vis[ux][uy][uz] = true;
s[ux][uy][uz] = '#';
q1.push(node(ux, uy, uz, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < l; k++)
if (s[i][j][k] == 'E') {
vis[i][j][k] = true;
s[i][j][k] = '#';
q2.push(node(i, j, k, 0));
}
while (!q1.empty() && !q2.empty()) {
if (q1.size() > q2.size()) swap(q1, q2);
int len1 = q1.size(), len2 = q2.size();
for (int i = 0; i < len1; i++) bfs(q1, vis);
for (int i = 0; i < len2; i++) {
node t = q2.front();
q2.pop();
int x = t.x, y = t.y, z = t.z, d = t.d;
if (vis[x][y][z]) return d + 1;
vis[x][y][z] = true;
s[x][y][z] = '#';
for (int j = 0; j < 6; j++) {
int kx = x + dx[j], ky = y + dy[j], kz = z + dz[j];
if (kx < 0 || kx >= n || ky < 0 || ky >= m || kz < 0 || kz >= l || vis[kx][ky][kz] || s[kx][ky][kz] == '#') continue;
q2.push(node(kx, ky, kz, d + 1));
}
}
}
return -1;
}
int main() {
while (scanf("%d%d%d", &n, &m, &l) == 3) {
if (n == 0 && m == 0 && l == 0) break;
getchar(); // 吸收换行符
for (int i = 0; i < n; i++) {
for (int j = 0; j < m;j++) {
fgets(s[i][j], MAXN, stdin);
sscanf(s[i][j], "%s", s[i][j]);
}
getchar(); // 吸收换行符
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < l; k++)
if (s[i][j][k] == 'S') {
ux = i, uy = j, uz = k;
break;
}
int res = bidirectional_bfs();
if (res == -1) printf("Trapped!\n");
else printf("Escaped in %d minute(s).\n", res);
}
return 0;
}
```
阅读全文