摘要：
Rescue )要进入网格。我们假设上下左右移动需要1个单位的时间，而上下移动也要1个单位时间。而且，我们也需要一个单位时间来完成所有的防护。您必须计算接近Angel的最小高度。输入第一行包含两个整数和NandM。接下来的n行，每行都有M个字符。“.”代表道路，“a”代表天使，和“r”代表每个天使朋友。处理到文件末尾。输出每个测试用例，您的程序应该输出一个整数，代表所需的一半。如果不存在这样的成员，您应该输出包含“PoorANGEL has stay in the life”的数据。示例输入78#。####。#.a#。#..r.#。#x……#。#。#……#……#####。#，2003年10月的描述：一位公主被俘。公主有很多朋友。A代表公主。R代表公主的朋友。#代表墙代表鲁X，守卫需要2秒才能击败守卫。现在让我们问问你的朋友谁能尽快救出公主。因为有不止一个朋友，我们可以通过BFS从公主那里搜索。因为击败后卫需要很长时间，所以我们选择了优先队列。每次我们进入最小的队列时，错误的代码都会通过dfs。它还应该通过1#include＜iostream＞2#include＜csdio＞3#include＜cmath＞4#include＜cs ring＞5#include＜algorithm＞6#include＜queue＞7#include＜map＞8#include＞9#include˂vector＞10#include＞cstdlib＞11#include˂string＞12#defineps0.00000000113typedeflonglongll；14种长LL型；15使用namespacestd；16组分N=1000+10；17英寸[N][N]；18英寸，m；19charmp[N][N]；20int_x[4]={0,1，-1,0}；21int_y[4]={1,0,0，-1}；22结构节点{23intx，y；24inttime；25friendboolopperb.time；27}28}a，b；29优先级_队列＜节点＞q；30intjudge｛31ifreturn0；32ifretrn0；33ifreturn 0；34return1；35｝36intBFS｛37a.time=0；38a.x=x；a.y=y；39q.push；40vis[x][y]=1；41while（！
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 29263 Accepted Submission(s): 10342
Problem Description
Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.
Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.
You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)
Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.
You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)
Input
First line contains two integers stand for N and M.
Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.
Process to the end of the file.
Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.
Process to the end of the file.
Output
For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."
Sample Input
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........
Sample Output
13
Author
CHEN, Xue
Source
题意：一个公主被抓 公主有很多个朋友 在图上 a代表公主 r 代表公主的朋友 #代表墙 .代表路 x代表守卫
打败守卫花费2秒 其它一秒 现在问你那个朋友能最快解救公主
因为朋友不止一个 我们可以BFS从公主开始搜 由于打败守卫花的时间长 我们选择优先队列 每次去最小
这题目数据很水 错的代码都能过 dfs应该也能过
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<queue> 7 #include<map> 8 #include<set> 9 #include<vector> 10 #include<cstdlib> 11 #include<string> 12 #define eps 0.000000001 13 typedef long long ll; 14 typedef unsigned long long LL; 15 using namespace std; 16 const int N=1000+10; 17 int vis[N][N]; 18 int n,m; 19 char mp[N][N]; 20 int _x[4]={0,1,-1,0}; 21 int _y[4]={1,0,0,-1}; 22 struct node{ 23 int x,y; 24 int time; 25 friend bool operator < (node a,node b){ 26 return a.time>b.time; 27 } 28 }a,b; 29 priority_queue<node>q; 30 int judge(int x,int y){ 31 if(x<0||x>=n||y<0||y>=m)return 0; 32 if(vis[x][y]==1)return 0; 33 if(mp[x][y]=='#')return 0; 34 return 1; 35 } 36 int BFS(int x,int y){ 37 a.time=0; 38 a.x=x;a.y=y; 39 q.push(a); 40 vis[x][y]=1; 41 while(!q.empty()){ 42 b=q.top(); 43 q.pop(); 44 for(int i=0;i<4;i++){ 45 int xx=b.x+_x[i]; 46 int yy=b.y+_y[i]; 47 if(judge(xx,yy)){ 48 vis[xx][yy]=1; 49 if(mp[xx][yy]=='x')a.time=b.time+2; 50 else if(mp[xx][yy]=='r')return (b.time+1); 51 else 52 a.time=b.time+1; 53 a.x=xx; 54 a.y=yy; 55 q.push(a); 56 } 57 } 58 } 59 return -1; 60 } 61 int main(){ 62 while(scanf("%d%d",&n,&m)!=EOF){ 63 while(!q.empty())q.pop(); 64 memset(vis,0,sizeof(vis)); 65 int x,y; 66 for(int i=0;i<n;i++) 67 for(int j=0;j<m;j++){ 68 cin>>mp[i][j]; 69 if(mp[i][j]=='a'){ 70 x=i;y=j; 71 //a.x=x;a.y=y;a.time=0; 72 } 73 } 74 int ans=BFS(x,y); 75 if(ans==-1) 76 printf("Poor ANGEL has to stay in the prison all his life. " ); 77 else 78 printf("%d ",ans); 79 } 80 }