hdu - 1242 Rescue && hdu - 2425 Hiking Trip (优先队列+bfs)

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

感觉题目没有表述清楚，angel的朋友应该不一定只有一个，那么正解就是a去搜索r,再用普通的bfs就能过了。

但是别人说要用优先队列来保证时间最优，我倒是没明白，步数最优跟时间最优不是等价的吗？就算士兵要花费额外时间，可是既然先到了目标点那时间不也一定是最小的？

当然用优先队列+ a去搜索r是最稳妥的。

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <iostream>

 using namespace std;

 struct maze

 {

     int x,y,t;

     bool operator < (const maze a) const

     {

         return t>a.t;

     }

 };

 int n,m,time;

 bool flag;

 char field[][];

 int dir[][]={{-,},{,},{,},{,-}};

 void bfs(maze s)

 {

     priority_queue<maze>que;

     que.push(s);

     while(!que.empty())

     {

         maze e=que.top();

         que.pop();

         for(int i=;i<;i++)

         {

             s.x=e.x+dir[i][];

             s.y=e.y+dir[i][];

             s.t=e.t+;

             if(s.x>=&&s.x<n&&s.y>=&&s.y<m&&field[s.x][s.y]!='#')

             {

                 if(field[s.x][s.y]=='r')

                 {

                     flag=;time=s.t;return;

                 }

                 else if(field[s.x][s.y]=='x') s.t++;

                 //printf("%d %d %d\n",s.x,s.y,s.t);

                 field[s.x][s.y]='#';

                 que.push(s);

             }

         }

     }

 }

 int main()

 {

     //freopen("a.txt","r",stdin);

     maze s;

     while(~scanf("%d%d",&n,&m))

     {

         getchar();

         for(int i=;i<n;i++)

         {

             scanf("%s",field[i]);

             for(int j=;j<m;j++)

             {

                 if(field[i][j]=='a')

                 {

                     s.x=i;

                     s.y=j;

                     s.t=;

                 }

             }

         }

         //printf("%d %d\n",s.x,s.y);

         flag=;

         field[s.x][s.y]='#';

         bfs(s);

         if(flag) printf("%d\n",time);

         else printf("Poor ANGEL has to stay in the prison all his life.\n");

     }

 }

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

这题是给定了起始点和目标点，让你求起始点到目标点的最少花费。总共有3种点，每一种点的花费都不同。跟上面那体没有很大区别。

这题简直悲剧，提交错了5，6次，就是一点小错误还害得我对拍了很多次。以后一定要细心。

判断到达目标点的时候不要再循环里面判断，可能出错。

 #include <cstdio>

 #include <cstring>

 #include <queue>

 using namespace std;

 struct maze

 {

     int x,y,cost;

     bool operator < (const maze a) const

     {

         return cost>a.cost;

     }

 };

 int r,c;

 int vp,vs,vt;

 int sr,sc,tr,tc;

 int dir[][]={{-,},{,},{,-},{,}};

 char field[][];

 int bfs()

 {

     priority_queue<maze>que;

     maze s;

     s.x=sr;s.y=sc;s.cost=;

     field[s.x][s.y]='@';

     que.push(s);

     while(!que.empty())

     {

         maze e=que.top();

         que.pop();

        // printf("%d %d %d\n",s.x,s.y,s.cost);

         if(e.x==tr&&e.y==tc) return e.cost;

         for(int i=;i<;i++)

         {

             s=e;

             s.x=e.x+dir[i][];

             s.y=e.y+dir[i][];

             if(s.x<||s.x>=r||s.y<||s.y>=c||field[s.x][s.y]=='@') continue;

             if(field[s.x][s.y]=='#') s.cost+=vp;

             else if(field[s.x][s.y]=='.') s.cost+=vs;

             else if(field[s.x][s.y]=='T') s.cost+=vt;

             field[s.x][s.y]='@';

             que.push(s);

         }

     }

     return -;

 }

 int main()

 {

     //freopen("data.txt","r",stdin);

     //freopen("b.txt","w",stdout);

     int j=;

     while(~scanf("%d%d",&r,&c))

     {

         //printf("%d %d\n",r,c);

         scanf("%d%d%d",&vp,&vs,&vt);

         //printf("%d %d %d\n",vr,vs,vt);

         getchar();

         for(int i=;i<r;i++) scanf("%s",field[i]);

         scanf("%d%d%d%d",&sr,&sc,&tr,&tc);

         printf("Case %d: %d\n",j++,bfs());

     }

     return ;

 }

巴特西

hdu - 1242 Rescue && hdu - 2425 Hiking Trip (优先队列+bfs)

最新文章

热门文章