HDU 1254(BFS)

快来打我* 2022-09-20 12:35 169阅读 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;
    }