HDU 1240(bfs)

红太狼 2022-09-20 11:28 127阅读 0赞

题意：给出一个三维空间，宇宙飞船的起始地点，目标地点，求最短飞行距离。

#include <iostream>
    #include <string>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    int N;
    
    int step[6][3] = { {1, 0 ,0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1} };
    
    char space[12][12][12];
    
    struct Point
    {
        int x, y, z, s;
        Point() : s(0) {}
        Point(int _x, int _y, int _z, int _s) : x(_x), y(_y), z(_z), s(_s) {}
        friend istream& operator >>(istream& is, Point& rhs)
        {
            is >> rhs.x >> rhs.y >> rhs.z;
            rhs.x += 1, rhs.y += 1, rhs.z += 1, rhs.s = 0;
            return is;
        }
        bool operator ==(const Point& rhs) const
        {
            return x == rhs.x && y == rhs.y && z == rhs.z;
        }
        Point operator +(const int S[]) const
        {
            return Point(x + S[0], y + S[1], z + S[2], s + 1);
        }
        bool legal()
        {
            return space[x][y][z] == 'O';
        }
        void visit()
        {
            space[x][y][z] = 'X';
        }
    } start, end;
    
    void BFS()
    {
        Point p, n;
        queue<Point> q;
        q.push(start);
        start.visit();
        while (!q.empty())
        {
            p = q.front();
            q.pop();
            for (int i = 0; i < 6; ++i)
            {
                n = p + step[i];
                if (!n.legal())
                    continue;
                else if (n == end)
                {
                    cout << N << " " << n.s << endl;
                    return;
                }
                else
                {
                    n.visit();
                    q.push(n);
                }
            }
        }
        cout << "NO ROUTE" << endl;
    }
    
    int main()
    {
        string temp;
        int i, j, k;
        for (i = 0; i < 12; ++i)
            for (j = 0; j < 12; ++j)
                space[0][i][j] = space[i][0][j] = space[i][j][0] = 'X';
        while (cin >> temp >> N)
        {
            for (i = 1; i <= N; ++i)
                for (j = 1; j <= N; ++j)
                    for (k = 1; k <= N; ++k)
                    {
                        cin >> space[j][k][i];
                        space[j][k][i] = toupper(space[j][k][i]);
                    }
            for (i = 0; i < 12; ++i)
                for (j = 0; j < 12; ++j)
                    space[N+1][i][j] = space[i][N+1][j] = space[i][j][N+1] = 'X';
            cin >> start >> end;
            cin >> temp;
            if (!(start.legal() && end.legal()))
            {
                cout << "NO ROUTE" << endl;
                continue;
            }
            else if (start == end)
            {
                cout << N << " " << 0 << endl;
                continue;
            }
            BFS();
        }
    }