HDU 1240(bfs)-蒲公英云

HDU 1240(bfs)

红太狼 2022-09-20 11:28 239阅读 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();
    }
}