HDU 2653 (记忆化BFS搜索+优先队列)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2653

题目大意：迷宫中有普通点和陷阱。其中普通点可以走可以飞，但是陷阱只能飞。走耗时1，飞耗时2。但是飞耗能1。给定一定能量P，问是否能在T秒内走出。

解题思路：

一开始SB似地认为每个点最多访问两次。其实每个点最多可以访问P次。

vis[X][Y][P]表示在(x,y)点能量为P的状态。

容易出错的地方在于这个组合: @. ,虽说是飞吧，但是还是会在陷阱上卡1s，尽管下一个点是. ,但是这种情况是必须飞的。

@@肯定是飞的，..这个就是可飞，可不飞。

BFS树明显是不均衡的，使用优先队列找到的第一个答案就可以return。

#include "cstdio"

#include "string"

#include "cstring"

#include "iostream"

#include "queue"

using namespace std;

char map[][];

int n,m,T,p,no,sx,sy,ex,ey,vis[][][],dir[][]={-,,,,,-,,};

struct status

{

    int x,y,dep,mana;

    status(int x,int y,int dep,int mana):x(x),y(y),dep(dep),mana(mana) {}

    bool operator < (const status &a) const {return dep > a.dep;}

};

int bfs(int x,int y,int mana)

{

    priority_queue<status> Q;

    Q.push(status(x,y,,mana));

    vis[x][y][mana]=;

    while(!Q.empty())

    {

        status t=Q.top();Q.pop();

        if(t.dep>=T) return -;

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

        {

            int X=t.x+dir[s][],Y=t.y+dir[s][];

            if(X<||X>n||Y<||Y>m||map[X][Y]=='#') continue;

            if(map[X][Y]=='@')

            {

                if(t.mana<||vis[X][Y][t.mana-]) continue;

                vis[X][Y][t.mana-]=true;

                Q.push(status(X,Y,t.dep+,t.mana-));

            }

            else

            {

                if(map[t.x][t.y]=='@'&&t.mana<) continue;

                if(X==ex&&Y==ey)

                {

                    if(t.mana>=) return t.dep+;

                    else return t.dep+;

                }

                if(t.mana>=||map[t.x][t.y]=='@')

                {

                    if(!vis[X][Y][t.mana-]) {vis[X][Y][t.mana-]=true;Q.push(status(X,Y,t.dep+,t.mana-));}

                }

                if(map[t.x][t.y]!='@'&&!vis[X][Y][t.mana]) {vis[X][Y][t.mana]=true;Q.push(status(X,Y,t.dep+,t.mana));}

            }

        }

    }

    return -;

}

int main()

{

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

    ios::sync_with_stdio(false);

    string tt;

    while(cin>>n>>m>>T>>p)

    {

        memset(vis,,sizeof(vis));

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

        {

            cin>>tt;

            for(int j=;j<tt.size();j++)

            {

                map[i][j+]=tt[j];

                if(tt[j]=='Y') {sx=i;sy=j+;}

                if(tt[j]=='L') {ex=i;ey=j+;}

            }

        }

        int ans=bfs(sx,sy,p);

        cout<<"Case "<<++no<<":"<<endl;

        if(ans>T||ans==-) cout<<"Poor Yifenfei, he has to wait another ten thousand years."<<endl;

        else cout<<"Yes, Yifenfei will kill Lemon at "<<ans<<" sec."<<endl;

    }

}

11892623

2014-10-17 12:22:29

Accepted

2653

218MS

2956K

2378 B

C++

Physcal