hdu1242 参考答案

   1 /*
   2 zju 1649 ,hdu 1242 最短路径 BFS
   3 ymc 2008/9/17
   4 题目大意：
   5 在一个n×m的地图上，天使用a表示，天使的一些朋友用r表示。＃表示墙，.表示路。
   6 x表示有一个守卫。r可以上下左右移动，每次只能移动一个点，需要1的时间。如果移到
   7 x的位置，需要额外1的时间杀掉x。
   8 求从r到a的最小时间
   9 解题思路：
  10 求所有r到其它点的的最短距离。
  11 dist[i][j]记录所有r到点i,j的最短距离，所有r的dist为0.
  12 used标记点i，j的最短距离是否已经求出。用BFS搜索a的距离。
  13 
  14 */
  15 #include <iostream>
  16 #include <queue>
  17 using namespace std;
  18 const int N=300;
  19 int dist[N][N];
  20 char graph[N][N];
  21 int step[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
  22 struct Pt
  23 {
  24         int x,y;
  25         int d;
  26         Pt(int xx=0,int yy=0,int dd=-1)
  27         {
  28                 x=xx;y=yy;d=dd;
  29         }
  30         bool operator<(const Pt &p)const
  31         {
  32                 return d>p.d;
  33         }
  34 };
  35 int n,m;
  36 int ax,ay;
  37 void BFS()
  38 {
  39 
  40         priority_queue<Pt> q;
  41         for(int i=0;i<n;i++)
  42                 for(int j=0;j<m;j++)
  43                 {
  44                         dist[i][j]=-1;
  45                         if(graph[i][j]=='a')
  46                         {
  47                                 ax=i;ay=j;
  48                         }
  49                         else if(graph[i][j]=='r')
  50                         {
  51                                 q.push(Pt(i,j,0));
  52                                 dist[i][j]=0;
  53                         }
  54                 }
  55         Pt u;
  56         int x1,y1;
  57         while(!q.empty())
  58         {
  59                 u=q.top();
  60                 q.pop();
  61                 if(u.x==ax && u.y== ay)
  62                         return ;
  63         for(int k=0;k<4;k++)
  64         {
  65             x1=u.x+step[k][0];
  66             y1=u.y+step[k][1];
  67             if(x1<0||x1>=n||y1<0||y1>=m)
  68                 continue;
  69             if(dist[x1][y1]>=0||graph[x1][y1]=='#')
  70                 continue;
  71             if(graph[x1][y1]=='x')
  72                 dist[x1][y1]=dist[u.x][u.y]+2;
  73             else
  74                 dist[x1][y1]=dist[u.x][u.y]+1;
  75             q.push(Pt(x1,y1,dist[x1][y1]));
  76         }
  77         }
  78 }
  79 int main()
  80 {
  81         while(cin>>n>>m)
  82         {
  83                 for(int i=0;i<n;i++)
  84                         for(int j=0;j<m;j++)
  85                                 cin>>graph[i][j];
  86                 BFS();
  87                 if(dist[ax][ay]>=0)
  88                         cout<<dist[ax][ay]<<endl;
  89                 else
  90                         cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
  91         }
  92 }