首页 > 搜索 > BFS搜索 > hdu 2653 Waiting ten thousand years for Love-优先队列-[解题报告]C++
2014
02-12

hdu 2653 Waiting ten thousand years for Love-优先队列-[解题报告]C++

Waiting ten thousand years for Love

问题描述 :

It was ten thousand years, after Demon Lemon caught Yifenfei’s love. In order to revenge and save his love, Yifenfei have been practising sword all day long and his Kongfu skills becomes so powerful that he can kill Demon Lemon immediately. Recently, Yifenfei have found Lemon’s castle, and now he is going to kill Lemon. At the same time, hearing about the terrible news, Demon Lemon is now preparing for escaping…

Now Yifenfei has got the map of the castle.
Here are all symbols of the map:
Only one ‘Y’ Indicates the start position of Yifenfei.
Only one ‘L’ Indicates the position of Demon Lemon.
‘.’ Indicate the road that Yifenfei can walk on it, or fly over it.
‘#’ Indicate the wall that Yifenfei can not walk or flay through it.
[email protected] Indicate the trap that Yifenfei can not walk on it, but can fly over it.

Yifenfei can walk or fly to one of up, down, left or right four directions each step, walk costs him 2 seconds per step, fly costs him 1 second per step and 1 magic power. His magic power will not increased, and if his magic power is zero, he can not fly any more.

Now Yifenfei asks you for helping him kill Demon Lemon smoothly. At the same time, Demon Lemon will Leave the castle Atfer T seconds. If Yifenfei can’t kill Demon Lemon this time, he have to wait another ten thousand years.

输入:

Lots of test cases, please process to end of file. In each test case, firstly will have four integers N, M, T, P(1 <= N, M, P <= 80, 1 <= T <= 100000), indicates the size of map N * M, the Lemon’s leaving time(after T seconds, Lemon will disappeared) and Yifenfei’s magic power. Then an N * M two-dimensional array follows indicates the map.

输出:

Lots of test cases, please process to end of file. In each test case, firstly will have four integers N, M, T, P(1 <= N, M, P <= 80, 1 <= T <= 100000), indicates the size of map N * M, the Lemon’s leaving time(after T seconds, Lemon will disappeared) and Yifenfei’s magic power. Then an N * M two-dimensional array follows indicates the map.

样例输入:

2 3 2 2
[email protected]
###
2 3 4 1
[email protected]
###
2 3 4 0
Y.L
###
2 3 3 0
Y.L
###

样例输出:

Case 1:
Yes, Yifenfei will kill Lemon at 2 sec.
Case 2:
Poor Yifenfei, he has to wait another ten thousand years.
Case 3:
Yes, Yifenfei will kill Lemon at 4 sec.
Case 4:
Poor Yifenfei, he has to wait another ten thousand years.



Hint
Hint Case 1: Yifenfei cost 1 second and 1 magic-power fly to [email protected], but he can not step on it, he must cost another 1 second and 1 magic-power fly to ‘L’ and kill Lemon immediately. Case 2: When Yifenfei Fly to [email protected], he has no power to fly, and is killed by trap.

/*
  这题题意:告诉起点Y的位置,然后告诉终点L的位置,然后输入 n, m, t ,p,其中 n和m是代表行和列,而t
  是时间,p代表能量,如果在t范围内没有找到L的话,就失败了,如果在t范围内找到了L,那么求出最少步数,
  .代表空地,可以走路过去,也可以飞过去,#代表不能走路过去,也不能飞过去,[email protected],但不能
  走路过去,所以要广搜的同时要用到优先队列,
  
  解题思路:
   BFS+优先队列
   我们可以先判断能不能飞过去,因为飞过去用的步数少,然后再考虑能不能走路过去
   走路过去的条件是,没有走过,[email protected],不然
   走下去根本没有意义


*/






#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N=85;
int n,m,t,p;
char s[N][N];
int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
bool visit[N][N][N];


struct node
{
    int x,y,step,pow;
    bool friend operator <(node a,node b) {
        return a.step>b.step;
    }
};


node start;
int bfs(int x,int y) {
    
    int i; 
    priority_queue<node>q;
    node cur,next;


    cur.x=x;
    cur.y=y;
    cur.step=0;
    cur.pow=p;
    visit[x][y][p]=1;


    q.push(cur);


    while(!q.empty()) {
        cur=q.top();
        q.pop();
        if(cur.step>t)return -1;
        if(s[cur.x][cur.y]=='L')return cur.step;


        for(i=0; i<4; i++) {
            next.x=cur.x+dir[i][0];
            next.y=cur.y+dir[i][1];
            if(next.x<0||next.x>=n||next.y<0||next.y>=m||s[next.x][next.y]=='#')continue;


            if(cur.pow>0&&!visit[next.x][next.y][cur.pow-1]) {
                visit[next.x][next.y][cur.pow-1]=1;
                next.pow=cur.pow-1;
                next.step=cur.step+1;
                q.push(next);
            }
            if(s[cur.x][cur.y]!='@'&&s[next.x][next.y]!='@'&&!visit[next.x][next.y][cur.pow]) {
                visit[next.x][next.y][cur.pow]=1;
                next.pow=cur.pow;
                next.step=cur.step+2;
                q.push(next);
            }


        }
    }
    return -1;


}
int main() {
    int tcase=0,i,j,flag;
    while(scanf("%d%d%d%d",&n,&m,&t,&p)!=EOF) {
        flag=0;
        memset(s,0,sizeof(s));
        for(i=0; i<n; i++)
            scanf("%s",&s[i]);
        for(i=0; i<n; i++) {
            for(j=0; j<m; j++) {
                if(s[i][j]=='Y') {
                    start.x=i;
                    start.y=j;
                    flag=1;
                    break;
                }
            }
            if(flag)break;
        }
        memset(visit,0,sizeof(visit));
        int num;
        num=bfs(start.x,start.y);
        printf("Case %d:\n",++tcase);
        if(num==-1)
            printf("Poor Yifenfei, he has to wait another ten thousand years.\n");
        else
            printf("Yes, Yifenfei will kill Lemon at %d sec.\n",num);
    }
    return 0;
}

解题转自:http://blog.csdn.net/u010195743/article/details/14229987


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!