萧峰被耶律洪基关进了监狱。 监狱被描述为一个 N * M (N, M <= 200) 的矩阵（矩阵中的一个元素称为一个网格）。 监狱里有墙、路和守卫。
萧峰的朋友们想要救他，就必须先到达萧峰所在的位置。 当网格中有守卫时，必须杀死他（或她）才能进入该网格。 由于萧峰的朋友们武功高强，可以杀死所有的守卫。
现假设向上、下、左、右移动一个网格需要 1 个单位时间，杀死一个守卫也需要 1 个单位时间（当然只能移动到边界内的相邻网格）。
现请帮忙计算朋友们到达萧峰所在位置的最短时间。
输入格式:

第一行包含两个整数，分别代表 N 和 M。
然后是 N 行，每行有 M 个字符，其中 “.” 代表道路， “#” 代表墙，“x” 代表守卫，“a”代表萧峰，“r”代表萧峰的朋友。
输出格式:

对于每个测试用例，您的程序应该输出一个整数，代表所需的最短时间。 如果不存在这样的数字，则应输出包含“No way!”的行。
输入样例:

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

输出样例:

13

#include <bits/stdc++.h>
using namespace std;
//结构体的优先队列：小根堆：重载> 大根堆：重载 <
struct Node {
    int x;
    int y;
    int time;

    bool operator>(const Node& other) const {
        return time > other.time;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    char grid[n][m];
    int start_x = -1, start_y = -1, end_x = -1, end_y = -1;

    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
            if (grid[i][j] == 'r') {
                start_x = i;
                start_y = j;
            } else if (grid[i][j] == 'a') {
                end_x = i;
                end_y = j;
            }
        }

    vector< vector<int> > dist(n, vector<int>(m, INT_MAX));
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    pq.push( {start_x, start_y, 0} );
    dist[start_x][start_y] = 0;

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        if (current.x == end_x && current.y == end_y) {
            cout << current.time << endl;
            return 0;
        }

        if (current.time > dist[current.x][current.y]) {
            continue;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#') {
                int new_time = current.time + 1;

                if (grid[nx][ny] == 'x') 
                    new_time ++;

                if (new_time < dist[nx][ny]) {
                    dist[nx][ny] = new_time;
                    pq.push( {nx, ny, new_time} );
                }
            }
        }
    }

    cout << "No way!" << endl;
    return 0;
}