因为在经过有禁卫的地方时，有2秒，所以图中的边的权值并不是都相等
所以，，我比较懒，，直接套用dijistra最短路了，233333333
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 200 + 5;
const int INF = 0x3f3f3f3f;
int vis[MX][MX];
char S[MX][MX];
int dist[][2] = {
{1, 0}, { -1, 0}, {0, 1}, {0, -1}};struct Point {int x, y, t;Point(int a, int b, int c) {x = a;y = b;t = c;}bool operator<(const Point &b)const {return t > b.t;}
};int main() {int m, n;while(~scanf("%d%d", &m, &n)) {memset(vis, INF, sizeof(vis));Point FST(-1, -1, 0);for(int i = 1; i <= m; i++) {scanf("%s", S[i] + 1);for(int j = 1; j <= n; j++) {if(S[i][j] == 'r') {FST = Point(i, j, 0);}}}if(FST.x == -1) {printf("Poor ANGEL has to stay in the prison all his life.\n");continue;}priority_queue<Point>work;work.push(FST);int ans = INF;while(!work.empty()) {Point fp = work.top();work.pop();vis[fp.x][fp.y] = fp.t;if(S[fp.x][fp.y] == 'a') {ans = fp.t;break;}for(int k = 0; k < 4; k++) {int nx = fp.x + dist[k][0];int ny = fp.y + dist[k][1];if(nx < 1 || nx > m || ny < 1 || ny > n) continue;if(S[nx][ny] == '#') continue;if(S[nx][ny] == '.' || S[nx][ny] == 'a') {if(vis[nx][ny] > fp.t + 1) {vis[nx][ny] = fp.t + 1;work.push(Point(nx, ny, fp.t + 1));}} else if(vis[nx][ny] > fp.t + 2) {vis[nx][ny] = fp.t + 2;work.push(Point(nx, ny, fp.t + 2));}}}if(ans == INF) {printf("Poor ANGEL has to stay in the prison all his life.\n");continue;} else {printf("%d\n", ans);}}return 0;
}