初学BFS，第一次用BFS做题。题目就是一个基本的BFS模型，需要稍加注意的是遇到警卫时间要+1，以及最后比的是最短的时间而不是步数。
#include<cstdio>
#include<cstring>
#include<queue>
#define s 205
#define INF 100000
using namespace std;
struct lo//建立结构体，存储点坐标和某种方法走到这里话费的步数和时间
{
int x,y,step,time;
};
queue<lo> q;//建立队列，存放结点
int mintime[s][s],dir[][]={{,},{,-},{-,},{,}},m,n,si,sj,ei,ej;//si、sj存储起点，mintime存储到某点最短时间，初始化为INF
char tem[s][s];//存储地图
int BFS(lo x)
{
int i;
q.push(x);
lo hd;
while(!q.empty())//为找到最优解，需要等到队列为空才能停止
{
hd=q.front();//拿出队列头，从队列头的结点开始继续走。
q.pop();
for(i=;i<;i++)
{
int x=hd.x+dir[i][],y=hd.y+dir[i][];
if(x>=&&x<m&&y>=&&y<n&&tem[x][y]!='#')//如果朝某个方向走一步可行，那么就判断这样是否是最短。若是，则压入
{
lo t;
t.x=x;t.y=y;t.time=hd.time+;t.step=hd.step+;
if(tem[x][y]=='x') t.time++;//如果是警卫，时间要+1
if(t.time<mintime[x][y])//或许有走到这里时间更短的方法，但既然每种都放入了队列，后来都会从这里继续走
{mintime[x][y]=t.time;
q.push(t);
}
}
}
}
return mintime[ei][ej];//返回答案
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
memset(tem,,sizeof(tem));
int i,j,an;
for(i=;i<m;i++)
{
scanf("%s",tem[i]);
}
for(i=;i<m;i++)
{
for(j=;j<n;j++)
{
mintime[i][j]=INF;//初始化时间都为INF
if(tem[i][j]=='a')
{
ei=i;ej=j;
}
else if(tem[i][j]=='r')
{
si=i;sj=j;
}
}
}
lo t;
t.x=si;t.y=sj;t.step=;t.time=;mintime[si][sj]=;
an=BFS(t);
if(an<INF)
printf("%d\n",an);
else
printf("Poor ANGEL has to stay in the * all his life.\n");
}
return ;
}