我爱崔老师系列之 BFS+优先队列+路径记录 HDU 1026 Ignatius and the Princess I(BFS）

崔老师推荐，用BFS找路径，然后由于一开始的时候不知道那个打架的时间要费时然后WA了一次，然后当时看见有discuss里说开头可能有怪兽然后又没加优先队列然后又WA了了一次，最后因为优先队列的那个排序错了又WA了一次，一晚上就只做了这一道题。。。悲哀= =。。。

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 char map[205][205];
  4 struct node
  5 {
  6     int x,y,step,f;//f存先驱，step是当前的步数。
  7 }q[400005];
  8 
  9 int way[400005];//用来最后存路径
 10 int f,r,m,n,fa,leap;
 11 int vis[205][205];
 12 int to[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};//四个方向
 13 void sort()//优先队列排序
 14 {
 15     int i;
 16     struct node t;
 17     for(i = r;i > f;i--)
 18     {
 19         if(q[i].step < q[i-1].step)
 20         {
 21             t = q[i];
 22             q[i] =q[i-1];
 23             q[i-1] = t;
 24         }
 25         else
 26         break;
 27     }
 28 }
 29 void bfs()
 30 {
 31     int i,j,nx,ny;
 32     memset(vis,0,sizeof(vis));
 33     f = r = 0;
 34     leap = 0;
 35     q[r].x = 0;
 36     q[r].y = 0;
 37     if(map[0][0] == 'X')//看看开头能不能走
 38     leap = 0;
 39     else
 40     {
 41 
 42     if(map[0][0] != '.'&& map[0][0] != 'X')//如果是数字的话开头是不能直接将STEP = 0 的。
 43     q[r].step = map[0][0]-'0';
 44     else
 45     q[r].step = 0;
 46     q[r].f = -1;
 47     vis[0][0] = 1;
 48     r++;
 49     while(f < r)
 50     {
 51         struct node now;
 52         fa = f;
 53         now = q[f++];
 54         for(i = 0;i < 4;i++)
 55         {
 56             nx = now.x+to[i][0];
 57             ny = now.y+to[i][1];
 58 
 59             if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] != 'X' && !vis[nx][ny])
 60             {
 61                 q[r].x = nx;
 62                 q[r].y = ny;
 63 
 64                 q[r].f = fa;
 65                 if(map[nx][ny] == '.')
 66                 q[r].step = now.step+1;
 67                 else
 68                 q[r].step = map[nx][ny]-'0'+now.step + 1;
 69 
 70                 if(nx == m-1 && ny == n-1)
 71                 {
 72                     leap = 1;
 73                     break;
 74                 }
 75                  sort();//优先队列排序。。。这里一定不要加错位置、
 76                 r++;
 77                 vis[nx][ny] = 1;
 78             }
 79         }
 80         if(leap)
 81         break;
 82     }
 83     }
 84 }
 85 int main()
 86 {
 87 
 88 
 89      
 90     int i,count,j,nt;
 91     while(~scanf("%d %d",&m,&n))
 92     {
 93         if(!(m||n))
 94         break;
 95         memset(map,0,sizeof(map));
 96         for(i = 0;i < m;i++)
 97         scanf("%s",map[i]);
 98         bfs();
 99         if(leap)
100         {
101             printf("It takes %d seconds to reach the target position, let me show you the way.\n",q[r].step);
102             count = -1;
103             while(1)
104             {
105                 way[++count] = r;
106                 r = q[r].f;
107                 if(r == -1)
108                 break;
109             }
110             nt = 1;
111             for(i = count;i > 0;i--)
112             {
113                 printf("%ds:(%d,%d)->(%d,%d)\n",nt++,q[way[i]].x,q[way[i]].y,q[way[i-1]].x,q[way[i-1]].y);
114                 if(map[q[way[i-1]].x][q[way[i-1]].y] != '.' )
115                 {
116                     int time;
117                     time = map[q[way[i-1]].x][q[way[i-1]].y]-'0';
118                     for(j = 0;j < time;j++)
119                     {
120                         printf("%ds:FIGHT AT (%d,%d)\n",nt++,q[way[i-1]].x,q[way[i-1]].y);
121                     }
122                 }
123             }
124 
125         }
126         else
127         puts("God please help our poor hero.");
128         puts("FINISH");
129     }
130     return 0;
131 }