kuangbin特集一Dungeon Master(BFS)
3 Dbfs、理屈は2 Dと同じです
コード:
コード:
// zyc 2018/8/20
#include
using namespace std;
const int maxn = 1e5 + 7;
char mp [100][100][100];
bool vis [100][100][100];
int fx [][3] = {0, 0, 1, 0, 0, -1, 0, 1, 0, 0, -1, 0, 1, 0, 0, -1, 0, 0};
int l, r, c;
struct node {
int x, y, z;
int step;
} ;
node s, e;
bool cheak (int i, int j, int k)
{
if (mp[i][j][k] != '#' && (!vis[i][j][k]) && i >= 0 && i < l && j >= 0 && j < r && k >= 0 && k < c)
return true;
return false;
}
void bfs ()
{
node s1, s2;
vis [s.x][s.y][s.z] = true;
queue res;
res.push(s);
while (!res.empty()) {
s1 = res.front ();
res.pop();
if (s1.x == e.x && s1.y == e.y && s1.z == e.z) {
printf ("Escaped in %d minute(s).
", s1.step);
return ;
}
for (int i = 0; i < 6; i ++) {
s2 = s1;
s2.x += fx[i][0];
s2.y += fx[i][1];
s2.z += fx[i][2];
if (cheak (s2.x, s2.y, s2.z)) {
vis [s2.x][s2.y][s2.z] = true;
s2.step ++;
res.push(s2);
}
}
}
puts ("Trapped!");
}
int main ()
{
while (~scanf ("%d %d %d", &l, &r, &c)) {
if (l == 0 && r == 0 && c == 0) return 0;
memset (vis, false, sizeof (vis));
for (int i = 0; i < l; i ++) {
for (int j = 0; j < r; j ++) {
scanf (" %s", mp[i][j]);
for (int k = 0; k < c; k ++) {
if (mp[i][j][k] == 'S') {
s.x = i, s.y = j, s.z = k;
s.step = 0;
} else if (mp[i][j][k] == 'E') {
e.x = i, e.y = j, e.z = k;
}
}
}
}
bfs ();
}
return 0;
}