HDU 1254(BFS)-蒲公英云

HDU 1254(BFS)

快来打我* 2022-09-20 12:35 295阅读 0赞

题意：如题。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int S[][3] = { {0, 1, 0}, {1, -1, 0}, {2, 0, 1}, {3, 0, -1} };
char map[9][9];
bool visit[9][9][4];
int M, N;
inline bool inMap(int x, int y)
{
    return x >= 0 && x < M && y >= 0 && y < N;
}
struct P
{
    int x, y;
    P() {}
    P(int _x, int _y) : x(_x), y(_y) {}
    bool operator ==(const P& rhs) const
    {
        return x == rhs.x && y == rhs.y;
    }
    friend ostream& operator <<(ostream& os, const P& rhs)
    {
        return os << "-----" << rhs.x << " " << rhs.y;
    }
};
struct Point
{
    int x, y, s;
    int p_x, p_y;
    Point() : s(-1) {}
    Point(int _x, int _y) : x(_x), y(_y), s(-1) {}
    Point(int _x, int _y, int _s) : x(_x), y(_y), s(_s) {}
    Point(int _x, int _y, int px, int py, int _s) : x(_x), y(_y), s(_s), p_x(px), p_y(py) {}
    void set(int _x, int _y, int _s)
    {
        x = _x, y = _y, s = _s;
    }
    bool operator ==(const Point& rhs) const
    {
        return x == rhs.x && y == rhs.y;
    }
    bool personCanGo(int bx, int by) const
    {
        if (bx == p_x && by == p_y) return true;
        //static bool flag;
        static int i, j;
        static P p, n;
        static int v[9][9];
        static queue<P> q1, q2;
        while (!q1.empty()) q1.pop();
        //while (!q2.empty()) q2.pop();
        for (i = 0; i < M; ++i)
            for (j = 0; j < N; ++j) v[i][j] = 0;
        //cout << p_x  << " ..... " << p_y << endl;
        q1.push(P(p_x, p_y));//, q2.push(P(bx, by));
        v[p_x][p_y] = 1;//, v[bx][by] = 2;
        while (!q1.empty())
        {
            p = q1.front(), q1.pop();
            //cout << "***" << p << endl;
            for (i = 0; i < 4; ++i)
            {
                n = P(p.x + S[i][1], p.y + S[i][2]);
            //    cout << n << endl;
                if (inMap(n.x, n.y) && map[n.x][n.y] == '0' && !(n.x == x && n.y == y))
                {
                    if (v[n.x][n.y])
                        continue;
                    if (n.x == bx && n.y == by)
                        return true;
                    v[n.x][n.y] = 1;
                    /*
                        for (j = 0; j < N; ++j) printf("%d",v[i][j]);
                    for (i = 0; i < M; ++i){
                        puts("");
                    }
                    puts("");
                    */
                //    cout << "push" << n << endl;
                    q1.push(n);
                }
            }
        }
        return false;
    }
    bool newPoint(int i, Point& rhs) const
    {
        int nx = x + S[i][1], ny = y + S[i][2];
        int bx = x - S[i][1], by = y - S[i][2];
        if (!(inMap(nx, ny) && inMap(bx, by)))
            return false;
        if (map[nx][ny] == '1' || visit[nx][ny][i] || map[bx][by] == '1')
            return false;
        if (!personCanGo(bx, by))
            return false;
        visit[nx][ny][i] = true;
        rhs = Point(nx, ny, x, y, s + 1);
        return true;
    }
} start, target;
int BFS(int M, int N)
{
    queue<Point> q;
    Point p, n;
    memset(visit, false, sizeof visit);
    q.push(start);
    while (!q.empty())
    {
        p = q.front(), q.pop();
        if (p == target)
            return p.s;
        for (int i = 0; i < 4; ++i)
            if (p.newPoint(i, n))
            {
                //printf("(%d, %d) ---> (%d, %d)\n", p.x, p.y, n.x, n.y);
                q.push(n);
            }
    }
    return -1;
}
int main()
{
    int T, i, j;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &M, &N);
        for (i = 0; i < M; ++i)
        {
            //scanf("%s", map[i]);
            for (j = 0; j < N; ++j)
            {
                scanf(" %c", &map[i][j]);
                if (map[i][j] == '2')
                    start.set(i, j, 0), map[i][j] = '0';
                else if (map[i][j] == '3')
                    target = Point(i, j), map[i][j] = '0';
                else if (map[i][j] == '4')
                    start.p_x = i, start.p_y = j, map[i][j] = '0';
            }
        }
        //for (i = 0; i < M; ++i)
        //    for (j = 0; j < N; ++j)
        //        putchar(map[i][j]);
        printf("%d\n", BFS(M, N));
    }
    return 0;
}