题目大意：有一个人关在监狱里，他有很多个朋友要去救他，求这些朋友救到他花费的最短时间，碰到警卫，他们就杀死警卫，要花费两个时间值
解题思路：看到最短消耗时间，想到了bfs，有因为有多个朋友r去解救Angel，所以想到以Angel的位置为起点，bfs求到任意一个朋友的位置花费最小的时间，之前直接就这么用bfs结果错了，忽略了碰到警卫是花费两个时间值，，而直接走只花费一个时间值，所以还得改造下。用一个二维数组来保存到达各个位置花费的时间，要是走到当前比这个位置原来花费的时间小，则更新值，才把这个状态加入队列中
#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;struct node{int x, y, step;};const int maxn = 210;int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int n, m, num, sx, sy, minv;char prison[maxn][maxn];int val[maxn][maxn];bool bfs();int main(){while(scanf("%d %d", &n, &m) != EOF){num = 0;memset(val, 0, sizeof(val));for(int i = 0; i < n; i++){scanf("%s", prison[i]);for(int j = 0; j < m; j++){if(prison[i][j] == ‘a’){sx = i;sy = j;}val[i][j] = 0x7fffffff;}}if(bfs())printf("%d\n", minv);elseprintf("Poor ANGEL has to stay in the prison all his life.\n");}return 0;}bool bfs(){queue<node> que;node s;s.x = sx;s.y = sy;s.step = 0;que.push(s);minv = 0x7fffffff;while(!que.empty()){node tmp = que.front();que.pop();if(prison[tmp.x][tmp.y] == ‘r’)minv = min(minv, tmp.step);for(int i = 0; i < 4; i++){int dx = tmp.x + dir[i][0];int dy = tmp.y + dir[i][1];if(dx >= 0 && dx < n && dy >=0 && dy < m && prison[dx][dy] != ‘#’){if(val[dx][dy] > tmp.step + 1){node next;next.x = dx;next.y = dy;next.step = tmp.step + 1;if(prison[dx][dy] == ‘x’)next.step++;val[dx][dy] = next.step;que.push(next);}}}}if(minv != 0x7fffffff)return true;return false;}
最美不过偷瞄你是你忽然转头，看见你的微笑
