HDU 1253(BFS)-蒲公英云

HDU 1253(BFS)

Dear 丶 2022-09-20 12:35 267阅读 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());
    }
}