HDU 1242(bfs)

偏执的太偏执、 2022-09-20 11:29 151阅读 0赞

题意：一个朋友拯救angel，'a' 是angel， 'x'是士兵， 'r'是朋友，'\#'是墙壁。没走一步花费一个单位的时间，遇到士兵与士兵搏斗花费一个单位的时间，求最短时间。

#include <iostream>
    #include <queue>
    #include <string>
    #include <sstream>
    using namespace std;
    
    struct Point
    {
        int x, y, time;
        bool operator <(const Point& rhs) const
        {
            return time > rhs.time;
        }
    } a;
    
    int direction[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
    
    void getXY(string* matrix, int n, int m)
    {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                if (matrix[i][j] == 'a')
                {
                    a.x = i;
                    a.y = j;
                    a.time = 0;
                    return;
                }
    }
    
    int result(string* matrix)
    {
        Point t;
        priority_queue<Point> q;
        Point p;
        q.push(a);
        while (!q.empty())
        {
            p = q.top();
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                t.x = p.x + direction[i][0];
                t.y = p.y + direction[i][1];
                if (matrix[t.x][t.y] == '#')
                    continue;
                t.time = p.time + 1;
                if (matrix[t.x][t.y] == 'r')
                    return t.time;
                if (matrix[t.x][t.y] == 'x')
                    t.time += 1;
                matrix[t.x][t.y] = '#';
                q.push(t);
            }
        }
        return -1;
    }
    
    int main()
    {
        int n, m, i;
        string line;
        string matrix[202];
        while (cin >> n >> m)
        {
            getchar();
            for (i = 1; i <= n; ++i)
            {
                getline(cin, matrix[i]);
                matrix[i] = '#' + matrix[i] + '#';
            }
            matrix[n+1] = matrix[0] = string(m+2, '#');
            getXY(matrix, n, m);
            i = result(matrix);
            if (i == -1)
                cout << "Poor ANGEL has to stay in the prison all his life.\n";
            else cout << i << endl;
        }
    }