acm题营救天使题意：天使（a）被困于迷宫,它的朋友（r）去救她,在迷宫中会有守卫（x）.r每走一步耗费一个单位的时间,如果路途遇上x,杀死x则需要一个单位的时间,求r找到a的最短时间.如

Question

acm 题 营救天使
题意：天使（a）被困于迷宫,它的朋友（r）去救她,在迷宫中会有守卫（x）.r每走一步耗费一个单位的时间,如果路途遇上x,杀死x则需要一个单位的时间,求r找到a的最短时间.如果找不到就输出"Poor ANGEL has to stay in the prison all his life."
样例输入：
7
8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#.
.
样例输出：13
我的代码：
#include
#include
using namespace std;
struct Node
{
int x,y;
int step;
}p,q,cur;
queue Q;
char map[210][210];
int m,n,startx,starty,endx,endy;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int bfs()
{
p.x=startx,p.y=starty,p.step=0;
Q.push(p);
while(!Q.empty())
{
cur=Q.front();
Q.pop();
if(cur.x==endx&&cur.y==endy)
{
return cur.step;
}
int i,xx,yy;
for(i=0;i>m>>n)
{
while(!Q.empty()) Q.pop();
memset(map,'#',sizeof(map));
startx=starty=endx=endy=-1;
for(i=1;imap[i][j];
if(map[i][j]=='r') startx=i,starty=j;
else if(map[i][j]=='a') endx=i,endy=j;
}
if(startx==-1||starty==-1||endx==-1||endy==-1) //测试用例里面有r不存在的情况
{
cout

Answer 1

bfs+优先队列