HDU 1253(BFS)

Dear 丶 2022-09-20 12:35 111阅读 0赞

题意：如题。

#include <iostream>
    #include <string>
    #include <cstring>
    #include <queue>
    #include <cstdio>
    using namespace std;
    int A, B, C, T;
    int step[6][3] = { {1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1} };
    int castle[52][52][52];
    struct Point
    {
        int x, y, z, t;
        Point() : t(0) {}
        Point(int _x, int _y, int _z, int _t) : x(_x), y(_y), z(_z), t(_t) {}
        Point operator +(const int s[]) const
        {
            return Point(x + s[0], y + s[1], z + s[2], t + 1);
        }
        bool legal()
        {
            return (castle[x][y][z] == 0) && t <= T;
        }
        bool end()
        {
            return x == A && y == B && z == C && t <= T;
        }
        void set()
        {
            castle[x][y][z] = 1;
        }
    };
    
    
    
    int BFS()
    {
        Point p, t;
        queue<Point> q;
        q.push(Point(1, 1, 1, 0));
        while (!q.empty())
        {
            p = q.front();
            q.pop();
            for (int i = 0; i < 6; ++i)
            {
                t = p + step[i];
                
                if (!t.legal())
                {
                    //cout << castle[t.x][t.y][t.z] <<endl;
                    continue;
                }
                //cout << castle[t.x][t.y][t.z] <<endl;
                if (t.end())
                    return t.t;
                t.set();
                //cout << t.x << " " << t.y << " " << t.z << endl;
                q.push(t);
            }
        }
        return -1;
    }
    
    int main()
    {
        int K, i, j, k;
        scanf("%d", &K);
        for (i = 1; i < 52; ++i)
            for (j = 1; j < 52; ++j)
                castle[0][i][j] = castle[i][j][0] = castle[i][0][j] = 1;
        while (K--)
        {
            scanf("%d%d%d%d", &A, &B, &C, &T);
            for (i = 1; i <= A; ++i)
                for (j = 1; j <= B; ++j)
                    for (k = 1; k <= C; ++k)
                        scanf("%d", &castle[i][j][k]);
            if (A + B + C - 3 > T)
            {
                puts("-1");
                continue;
            }
            
            for (i = 1; i < 52; ++i)
                for (j = 1; j < 52; ++j)
                    castle[A+1][i][j] = castle[i][j][C+1] = castle[i][B+1][j] = 1;
            
            /*
            for (i = 1; i <= B; ++i)
                for (j = 1; j <= C; ++j)
                    castle[A+1][i][j] = 1;
            for (i = 1; i <= A; ++i)
                for (j = 1; j <= B; ++j)
                    castle[i][j][C+1] = 1;
            for (i = 1; i <= A; ++i)
                for (j = 1; j <= C; ++j)
                    castle[i][B+1][j] = 1;
                    */
            printf("%d\n", BFS());
        }
    }