题目链接：http://icpc.njust.edu.cn/Problem/Hdu/1242/
这次的迷宫是有守卫的，杀死一个守卫需要花费1个单位的时间，所以以走的步数为深度，在每一层进行搜索，由于走一步的花费不一定是1，所以我们需要用优先队列寻找最优值。这个题目真是模板题。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define pf printf
#define mem(a,b) memset(a,b,sizeof(a))
#define prime1 1e9+7
#define prime2 1e9+9
#define pi 3.14159265
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define scand(x) scanf("%llf",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define scan(a) scanf("%d",&a)
#define dbg(args) cout<<#args<<":"<<args<<endl;
#define inf 0x3f3f3f3f
#define maxn 205
int n,m,t;
int sx,sy,tx,ty;
bool vis[maxn][maxn];
char Map[maxn][maxn];
int dir[][]={,,,-,,,-,};
struct node{
int x,y,time;
node(int x,int y,int s):x(x),y(y),time(s){}
node(){}
friend operator< (node a,node b)
{
return a.time>b.time;//逆定义运算符
}
};
int ans=;
node cur,nxt;
void bfs()
{
priority_queue<node>q;
q.push(node(sx,sy,));
vis[sx][sy]=;
while(!q.empty())
{
cur=q.top();
q.pop();
if(cur.x==tx&&cur.y==ty)
{
ans=cur.time;
return;
}
f(i,,)
{
nxt=cur;
nxt.x+=dir[i][];
nxt.y+=dir[i][];
nxt.time++;
if(nxt.x<||nxt.x>n||nxt.y<||nxt.y>m||Map[nxt.x][nxt.y]=='#')continue;
if(vis[nxt.x][nxt.y])continue;
vis[nxt.x][nxt.y]=;
if(Map[nxt.x][nxt.y]=='x')nxt.time++;
q.push(nxt);
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
std::ios::sync_with_stdio(false);
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=;
mem(vis,false);
f(i,,n)
f(j,,m)
{
scanf(" %c",&Map[i][j]);
if(Map[i][j]=='r')sx=i,sy=j;
if(Map[i][j]=='a')tx=i,ty=j;
}
bfs();
if(!ans)pf("Poor ANGEL has to stay in the * all his life.\n");
else pf("%d\n",ans);
} }