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; }