BFS+优先队列（目标有多个，导致平常的BFS搜索到的不一定是最佳）

Angel所在的位置是a;  Angel的朋友用r表示, Angel可能有多个朋友 ,也就是可能有多个r ;   #表示墙  ;x表示警卫  ,可能会有多个警卫;
Angel的朋友要进入a  只能上下左右的走， 每走一个格用一个单位时间，如果遇上警卫，杀掉警卫要花一个单位时间   问Angel能否救到

angel,
如果能 求最少的时间被这道题的有两个地方震了
   1.有多个r搜r到a有多条路最后比较   但是倒过来想 从a搜到r就搜一条最佳路
   2.涉及到一个杀警卫的时间，所以queue队列中的node 不是按时间大小排列的, 用priority_queue,
  第一学着次用priority_queue, 在此感谢cxl 

与平常的BFS不同，目标有多个，那么BFS搜索到的目标点不一定是最小的，
所以每次拿最小的时间点来扩展（而不是平常的先进先出点来扩展）

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn = 201;
struct Node {
    int x, y, tme;
    friend bool operator < (const Node &a, const Node &b) {
        return a.tme > b.tme;
    }//时间从小到大
};

int n, m;
int sx, sy;
char map[maxn][maxn];
int mark[maxn][maxn];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool Overmap(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) {
        return true;
    }
    return false;
}

inline int BFS() {
    memset(mark, 0, sizeof(mark));
    priority_queue<Node> Q;
    Node first, next;
    first.x = sx, first.y = sy;
    first.tme = 0;
    mark[sx][sy] = true;
    Q.push(first);
    while (!Q.empty()) {
        first = Q.top();
        Q.pop();
        //找到，退出
        if (map[first.x][first.y] == 'r') {
            return first.tme;
        }
        //四次循环分别对应四个方向
        for (int i = 0; i < 4; i++) {
            next.x = first.x + dir[i][0];
            next.y = first.y + dir[i][1];
            if (Overmap(next.x, next.y) || map[next.x][next.y] == '#' || mark[next.x][next.y]) {
                continue;
            }
            if (map[next.x][next.y] == 'x') {
                next.tme = first.tme + 2;
            } else {
                next.tme = first.tme + 1;
            }
            mark[next.x][next.y] = 1;//标志已经走过的点
            Q.push(next);//入队对它进行扩展
        }
    }
    return -1;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 0; i < n; i++) {
            scanf("%s", map[i]);
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'a') {
                    sx = i, sy = j;
                }
            }
        }//for(i)
        int res = BFS();
        if (res == -1) {
            puts("Poor ANGEL has to stay in the prison all his life.");
        } else {
            printf("%d\n", res);
        }
    }
    return 0;
}