hdu 1242 Rescue

题目意思：friends用最短的时间去救angel '.'表示通道 '#'表示墙壁 'x'表示guard

走一格要一单位时间，杀死一个guard要一个单位时间

如果可以救求最短时间，否则按要求输出

解题思路：bfs 对'x'做下处理 具体见下代码

code：

#include
#include
const int size=100005;

int p[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
typedef struct da
{
  int x;
  int y;
  int time;       
}da;

da que[size];
char ch[201][201];
int f[201][201];

int main()
{
    int m,n,i,j,rear,front,x,y,xx,yy,st,en,time;
    int x1,y1,x2,y2,k,flag,an;
   while(scanf("%d%d",&m,&n)!=EOF)
   {
    k=1;
    for(i=0;i    {
    scanf("%s",ch[i]);
      for(j=0;j      {
      if(ch[i][j]=='r')
      {x1=i;y1=j;k++;}             
      }               
    }
    front=0;rear=1;
    que[rear].x=x1;que[rear].y=y1;
    que[rear].time=0;
    memset(f,0,sizeof(f));
    f[x1][y1]=1;flag=0;
    while(front    {
       st=front;en=rear;
       for(i=st+1;i<=en;i++)
       {
       x=que[i].x;y=que[i].y;time=que[i].time;
       if(ch[x][y]=='a') {flag=1;an=time;break;}
       if(ch[x][y]=='x')  //特殊处理
       {
       rear++;
       que[rear].x=x;que[rear].y=y;que[rear].time=time+1;    
       ch[x][y]='.';     //注意这里不可以少       
       }
       else
          //四个方向
          for(j=0;j<4;j++)
          {
          xx=x+p[j][0];yy=y+p[j][1];
          if(xx<0||xx>=m||yy<0||yy>=n) continue;
          if(f[xx][yy]) continue;
          if(ch[xx][yy]=='#') continue;
          rear++;
          que[rear].x=xx;que[rear].y=yy;que[rear].time=time+1; 
          f[xx][yy]=1;            
          }                  
       }
       front=en;                
    }
    if(flag) printf("%d\n",an);
    else printf("Poor ANGEL has to stay in the prison all his life.\n");
   }   
}