这道题和前几天做的一道题很像，都是bfs+优先队列，但是这道题多了一个路径输出

自己写的很乱，即使过了。。。也可能是数据太水才过了的

看了一下大牛的博客竟然0ms。。。

贴过来学习一下，写的真的条理清晰，包括最后的路径记录也是用了方向记录数组和递归 很巧妙

原博客：https://blog.csdn.net/ice_crazy/article/details/7763302

亮点：

三个数组用来记录：

map数组用来记录这个地方是否可以走，以及走这个地方需要多少秒，值为-1（不可走）0（可走）或者其他别的（几秒钟）

剩下两个用来记录路径：flag为从上一步到达这一步的方向，或者最初的第一步（值为0）；blood用来还原这一步的击杀怪兽时间。

#include"stdio.h"  #include"string.h"  #include"queue"  using namespace std;    struct node  {      int x,y;      int step;      friend bool operator<(node n1,node n2)      {          return n2.step
     
      =n || y<0 || y>=m)  return 1;      if(map[x][y]==-1)               return 1;      return 0;  }  int BFS()  {      priority_queue
      
       q;      node cur,next;      int i;        cur.x=0;      cur.y=0;      cur.step=0;      map[0][0]=-1;        q.push(cur);      while(!q.empty())      {          cur=q.top();          q.pop();          if(cur.x==n-1 && cur.y==m-1)    return cur.step;          for(i=0;i<4;i++)          {              next.x=cur.x+dir[i][0];              next.y=cur.y+dir[i][1];                if(judge(next.x,next.y))    continue;              next.step=cur.step+1+map[next.x][next.y];              flag[next.x][next.y]=i+1;              map[next.x][next.y]=-1;              q.push(next);          }      }      return -1;  }  int temp;  void P(int x,int y)  {      int next_x,next_y;      if(flag[x][y]==0)   return ;      next_x=x-dir[flag[x][y]-1][0];      next_y=y-dir[flag[x][y]-1][1];      P(next_x,next_y);      printf("%ds:(%d,%d)->(%d,%d)\n",temp++,next_x,next_y,x,y);        while(blood[x][y]--)    printf("%ds:FIGHT AT (%d,%d)\n",temp++,x,y);  }    int main()  {      char str[111];      int i,l;      int ans;        while(scanf("%d%d",&n,&m)!=-1)      {          memset(map,0,sizeof(map));          memset(flag,0,sizeof(flag));          memset(blood,0,sizeof(blood));          for(i=0;i