hdu 1026(BFS+输出路径) 我要和怪兽决斗

http://acm.hdu.edu.cn/showproblem.php?pid=1026

模拟一个人走迷宫,起点在(0,0)位置,遇到怪兽要和他决斗，决斗时间为那个格子的数字,就是走一个格子花费时间1,

遇到有数字的格子还要花费这个数字大小的时间,输出最后走到(n-1,m-1)的最小时间,还要输出他的路径，'X'是墙,‘.’是可以走的空地

就是这个路径,刚一看题看到那个样例输出吓得我都飞起来了,好多啊！

其实还好啦,广搜,一开始还因为是普通的广搜,后来发现不一样,

为了寻求最小时间,他可以选择走有数字的格子也可以选择绕过去,看哪个时间短一些

首先求出最小时间,跟那个连连看差不多,用visit数组初始化很大,来储存到达每个点的最小时间

然后输出路径的时候用递归回溯,因为广搜是广泛的搜索,并不能保证走过的点都是最短路径上的点

所以从终点开始利用他的方向来往前回溯,注意因为没有用优先队列和输出漏了句号所以刚开始wa了几发

code

  1 #include<cstdio>
  2 #include<climits>
  3 #include<queue>
  4 #include<cstring>
  5 using namespace std;
  6 char map[111][111];
  7 int visit[111][111];
  8 int flag[111][111];
  9 struct point{
 10     int x,y;
 11     int time;
 12     friend bool operator<(point n1,point n2)
 13     {
 14         return n2.time<n1.time;
 15     }
 16 };
 17 int n,m,t;
 18 int dx[]={1,0,0,-1};
 19 int dy[]={0,-1,1,0};
 20 int bfs()
 21 {
 22     int i;
 23     priority_queue<point>Q;
 24     point now,next;
 25     now.x=0;now.y=0;
 26     now.time=0;
 27     visit[0][0]=0;
 28     Q.push(now);
 29     while (!Q.empty())
 30     {
 31         now=Q.top();
 32         Q.pop();
 33         if (now.x==n-1&&now.y==m-1)
 34             return visit[now.x][now.y];
 35         for (i=0;i<4;i++)
 36         {
 37             next.x=now.x+dx[i];
 38             next.y=now.y+dy[i];
 39             if (next.x<0||next.x>=n||next.y<0||next.y>=m)continue;
 40             if (map[next.x][next.y]=='X')continue;
 41             if (map[next.x][next.y]=='.')
 42                  next.time=now.time+1;
 43             else
 44                  next.time=now.time+1+(map[next.x][next.y]-'0');
 45             if (map[next.x][next.y]<='9'&&map[next.x][next.y]>='1'&&visit[next.x][next.y]>now.time+(map[next.x][next.y]-'0'))
 46             {
 47                  visit[next.x][next.y]=now.time+1+(map[next.x][next.y]-'0');
 48                  flag[next.x][next.y]=i+1;
 49                  Q.push(next);
 50             }
 51             else if (map[next.x][next.y]=='.'&&visit[next.x][next.y]>now.time+1)
 52             {
 53                 visit[next.x][next.y]=now.time+1;
 54                 flag[next.x][next.y]=i+1;
 55                 Q.push(next);
 56             }
 57         }
 58     }
 59     return -1;
 60 }
 61 void output(int x,int y)//回溯
 62 {
 63     int sx,sy;
 64     if (flag[x][y]==0)  return ;
 65     sx=x-dx[flag[x][y]-1];
 66     sy=y-dy[flag[x][y]-1];
 67     output(sx,sy);
 68     printf("%ds:(%d,%d)->(%d,%d)
",t++,sx,sy,x,y);
 69     if (map[x][y]<='9'&&map[x][y]>='0')
 70     {
 71         int w=map[x][y]-'0';
 72         while (w--)
 73             printf("%ds:FIGHT AT (%d,%d)
",t++,x,y);
 74     }
 75 }
 76 int main()
 77 {
 78     int i,j,q;
 79     while (~scanf("%d %d",&n,&m))
 80     {
 81         getchar();
 82         for (i=0;i<n;i++)
 83         {
 84             for (j=0;j<m;j++)
 85                 scanf(" %c",&map[i][j]);
 86         }
 87         for (i=0;i<n;i++)
 88         for (j=0;j<m;j++)
 89         {
 90             visit[i][j]=INT_MAX;
 91             flag[i][j]=0;
 92         }
 93         q=bfs();
 94         if (q==-1)
 95         {
 96             puts("God please help our poor hero.");
 97             puts("FINISH");
 98         }
 99         else
100         {
101             printf("It takes %d seconds to reach the target position, let me show you the way.
",q);
102             t=1;
103             output(n-1,m-1);
104             puts("FINISH");
105         }
106     }
107     return 0;
108 }