今天刚复习完bfs。来做这道题爽一爽。
洛谷题号:P2360 地下城主
首先这道题用dfs肯定会非常干净利落地解决您多年的脑血栓(使用的前提是你愿意彻底放松一下爽一把)别问我怎么知道的
所以,还有谁能解决呢?没错,是我们的bfs。
在这里相信大家一定精通了bfs模板。这道题其实就是把模板改成三维,基本上没有细节和需要注意的地方。
首先,是方向数组和各项变量和数组的初始化
const int N = 50;
char a[N][N][N];
int vis[N][N][N];
int l, r, c, sx, sy, sz, ex, ey, ez;
int dx[] = {0, 1, 0, -1, 0, 0};
int dy[] = {1, 0, -1, 0, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};
当然,结构体也少不了
struct node {
int x, y, z;
};
然后设置int sx, sy, sz
和int ex, ey, ej
来记录起始位置和终点。
for (int i = 1; i <= l; i++) {
for (int j = 1; j <= r; j++) {
for (int k = 1; k <= c; k++) {
cin >> a[i][j][k];
if (a[i][j][k] == 'S') {
sx = i, sy = j, sz = k;
} else if (a[i][j][k] == 'E') {
ex = i, ey = j, ez = k;
}
}
}
}
然后就是bfs内部构造了(只展示核心代码)
for (int i = 0; i < 6; i++) {
int nx = xx + dx[i];
int ny = yy + dy[i];
int nz = zz + dz[i];
if (nx >= 1 && ny >= 1 && nz >= 1 && nx <= l && ny <= r && nz <= c &&
a[nx][ny][nz] != '#' && vis[nx][ny][nz] == 0) {
vis[nx][ny][nz] = vis[xx][yy][zz] + 1;
q.push({nx, ny, nz});
}
}
最后的最后,做判断输出
int ans = bfs();
if (ans == -1) {
cout << "Trapped!" << endl;
} else {
cout << "Escaped in " << ans << " minute(s)." << endl;
}
最后,就可以AC了