HDU1175(bfs)

柔光的暖阳◎ 2022-09-20 11:23 203阅读 0赞

题意：如题。

#include <iostream>
    #include <queue>
    #include <string>
    #include <cstring>
    #include <sstream>
    using namespace std;
    
    #define LEFT 3
    #define RIGHT 2
    #define UP 1
    #define DOWN 0
    #define EMPTY -1
    
    int step[4][3] = { {0, 1, 0}, {1, -1, 0}, {2, 0, 1}, {3, 0, -1} };
    
    
    struct Point
    {
        int x, y;
        int lx, ly;
        int ld; // last direction
        int turn;
        Point() : x(int()), y(int()), ld(EMPTY), turn(0), lx(-1), ly(-1) {}
        Point(int _x, int _y, int t, int l, int _lx, int _ly) : x(_x), y(_y), turn(t), ld(l), lx(_lx), ly(_ly)  {}
        friend istream& operator >>(istream& is, Point& p)
        {
            return is >> p.x >> p.y;
        }
        bool operator ==(const Point& rhs) const
        {
            return x == rhs.x && y == rhs.y;
        }
        Point operator +(int s[]) const
        {
            int t = turn;
            if (ld != EMPTY && ld != s[0])
                t += 1;
            if (x + s[1] == lx && y + s[2] == ly)
                t = 3;
            return Point(x + s[1], y + s[2], t, s[0], x, y);
        }
        bool isOk()
        {
            return turn <= 2;
        }
        bool operator <(const Point& rhs) const
        {
            return turn > rhs.turn;
        }
    };
    
    inline char& getChar(string* matrix, Point& p)
    {
        return matrix[p.x][p.y];
    }
    
    bool isOk(string* matrix, Point& a, Point& b)
    {
        char _a = getChar(matrix, a), _b = getChar(matrix, b);
        if (a == b)
            return false;
        if (_a != _b)
            return false;
        if (_a == '0')
            return false;
        return true;
    }
    
    bool BFS(string* matrix, Point& a, Point& b)
    {
        if (!isOk(matrix, a, b))
            return false;
        Point p, n;
        priority_queue<Point> q;
        q.push(a);
        while (!q.empty())
        {
            p = q.top();
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                n = p + step[i];
                if (!n.isOk())
                    continue;
                if (n == b)
                    return true;
                if (getChar(matrix, n) != '0')
                    continue;
                if (n.turn == 2 && n.x != b.x && n.y != b.y)
                    continue;
                q.push(n);
            }
        }
        return false;
    }
    
    int main()
    {
        int n, m, i, q, j;
        Point a, b;
        string matrix[1002];
        while (cin >> n >> m, n || m)
        {
            for (i = 1; i <= n; ++i)
            {
                matrix[i] = "";
                for (j = 1; j <= m; ++j)
                {
                    cin >> q;
                    matrix[i] = matrix[i] + char(q + '0');
                }
                matrix[i] = '1' + matrix[i] + '1';
            }
            matrix[0] = matrix[n+1] = string(m+2, '1');
            cin >> q;
            while (q--)
            {
                cin >> a >> b;
                // cout << a.x << " " << a.y << " " << b.x << " " << b.y << endl;
                cout << (BFS(matrix, a, b) ? "YES" : "NO") << endl;
            }
        }
    }