HDU 1180(bfs)

灰太狼 2022-09-20 11:25 150阅读 0赞

题意：如题。

#include <iostream>
    #include <string>
    #include <sstream>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    struct Point
    {
        int x, y, time;
        bool operator <(const Point& rhs) const
        {
            return time > rhs.time;
        }
        Point() {}
        Point(int _x, int _y, int _t) : x(_x), y(_y), time(_t) {}
        Point operator +(int s[]) const
        {
            return Point(x + s[0], y + s[1], time);
        }
    };
    
    int step[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
    
    void getPoint(string* maze, int m, int n, Point& p, char c)
    {
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
            {
                if (maze[i][j] == c)
                {
                    p.x = i;
                    p.y = j;
                    return;
                }
            }
    }
    
    inline char& getChar(string* maze, Point& p)
    {
        return maze[p.x][p.y];
    }
    
    int BFS(string* maze, int m, int n)
    {
        char c;
        Point start(0, 0, 0), p, t;
        getPoint(maze, m, n, start, 'S');
        // getPoint(maze, m, n, target, 'T');
        priority_queue<Point> q;
        q.push(start);
        getChar(maze, start) = '*';
        while (!q.empty())
        {
            p = q.top();
            q.pop();
            if (p.x == -1)
                return p.time;
            for (int i = 0; i < 4; ++i)
            {
                t = p + step[i];
                c = getChar(maze, t);
                if (c == '*')
                    continue;
                if (c == '-' || c == '|')
                {
                    if (getChar(maze, t + step[i]) == '*')
                        continue;
                    if (p.time & 1)
                        c = c == '-' ? '|' : '-';
                    t = t + step[i];
                    if (!(c == '-' && i < 2 || (c == '|' && i >= 2)))
                        t.time += 1;
                    c= getChar(maze, t);
                }
                t.time += 1;
                if (c == 'T')
                    t.x = t.y = -1;
                else
                    getChar(maze, t) = '*';
                q.push(t);
            }
        }
        return -1;
    }
    
    int main()
    {
        int m, n, i;
        string maze[22];
        while (cin >> m >> n)
        {
            getchar();
            for (i = 1; i <= m; ++i)
            {
                getline(cin, maze[i]);
                maze[i] = '*' + maze[i] + '*';
            }
            maze[0] = maze[m + 1] = string(n+2, '*');
            cout << BFS(maze, m, n) << endl;
        }
    }