Dungeon Master
Dungeon Master经典!经典!!经典!!!广搜题,一开始自己尝试解决没能成功,后来看了题解我大为震撼,包含了不少我需要具备的思想,值得细细品味这道题://我愿意称之为搜索的典型例题!!!(太经典了)//认真吸收里面的思想!!//广搜解法#include<iostream>#include<cstdio>#include<cstring>#include
·
Dungeon Master
经典!经典!!经典!!!
广搜题,一开始自己尝试解决没能成功,后来看了题解我大为震撼,包含了不少我需要具备的思想,值得细细品味这道题:
//我愿意称之为搜索的典型例题!!!(太经典了)
//认真吸收里面的思想!!
//广搜解法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int l, r, c;
int step[40][40][40];//!!利用方块的数字记录了到达此处的步数!(好处大大滴:直接可知道终点坐标处的步数!!)
char cube[40][40][40];//存放输入
int dx[] = { 1,0,0,-1,0,0 };//经典利用数组进行移动遍历
int dy[] = { 0,1,0,0,-1,0 };
int dz[] = { 0,0,1,0,0,-1 };
int sx, sy, sz, ex, ey, ez;//记录入口和出口坐标
struct cub {//又是结构体!记录方块坐标显得整齐
int x, y, z;
};
queue<cub>q;
void bfs() {
while (!q.empty()) {
cub t = q.front();//在循环内赋值出队(一开始写在 while 外面了!!)
q.pop();
for (int i = 0;i < 6;i++) {//遍历移动
int nx = t.x + dx[i];
int ny = t.y + dy[i];
int nz = t.z + dz[i];
if (nx > 0 && ny > 0 && nz > 0 && nx <= l && ny <= r && nz <= c && step[nx][ny][nz] == -1 && cube[nx][ny][nz] == '.') {
step[nx][ny][nz] = step[t.x][t.y][t.z] + 1;//计算步数(每次加一)
cub p;
p.x = nx;p.y = ny;p.z = nz;
q.push(p);//符合条件的格子入队
}
}
}
//判断终点步数
if (step[ex][ey][ez] == -1) cout << "Trapped!" << endl;
else cout << "Escaped in " << step[ex][ey][ez] << " minute(s)." << endl;
}
int main() {
while (cin >> l >> r >> c && (l || r || c)) {
memset(step, -1, sizeof(step));//每次循环初始化(注意要初始化为 -1!因为起点处是 0)
for (int i = 1;i <= l;i++) {
for (int j = 1;j <= r;j++) {
for (int k = 1;k <= c;k++) {
cin >> cube[i][j][k];
if (cube[i][j][k] == 'E') {
ex = i;ey = j;ez = k;
cube[i][j][k] = '.';//关键!!!将终点也变为 . 号
}
if (cube[i][j][k] == 'S') {
sx = i;sy = j;sz = k;
}
}
}
getchar();//吸收输出的行间空行
}
step[sx][sy][sz] = 0;//起点记为 0 步
cub cu;
cu.x = sx;cu.y = sy;cu.z = sz;
q.push(cu);
bfs();//从起点开始搜索
}
return 0;
}
细节拉满,放到注释里了~
数据结构与算法,只要有你在我就会努力~!!
更多推荐
已为社区贡献2条内容
所有评论(0)