FZU-2124: 吃豆人

搜索

Description

吃豆人是一款非常经典的游戏，游戏中玩家控制吃豆人在地图上吃光所有豆子，并且避免被怪物抓住。

这道题没有怪物，将游戏的画面分成n*m的格子，每格地形可能为空地或者障碍物，吃豆人可以在空地上移动，吃豆人每移动一格需要1s时间，并且只能朝上下左右四个方向移动，特别的是吃豆人还能吐出舌头，舌头每移动一格需要0.1s时间，舌头只可以走直线。不必考虑吃豆人转身所需要的时间。

举例，吃豆人在(1,1)坐标，而豆子在(1,5)坐标，并且中间没有障碍物，此时朝豆子方向吐舌头～，经过0.8s就可以吃到豆子(来回各0.4s,吐出去的舌头要缩回来的嘛)。

游戏中还有加速道具，一旦得到加速道具，吃豆人就获得2倍移动速度，吐舌头的速度没有增加，即走1格用0.5s。现在地图上有且只有一颗豆子。游戏中有.代表空地；X表示障碍，吃豆人不能越过障碍；B代表豆子；S代表加速道具，并且地图上道具总数不超过1个，道具所在的位置为空地，得到道具后立即使用，道具立即消失，地形变为空地，不能用舌头去取道具；P表示吃豆人,吐舌头的时候吃豆人不能移动。

Input

输入包含多组数据。输入第一行有两个个整数n,m(2<=n,m<=20)，接着一个n*m的地图矩阵。

对于50%的数据，地图上没有道具。

Output

输出一行，最快用多少s吃到豆子,结果保留1位小数，如果吃不到，输出-1。

Sample Input

2 2
XP
B.
3 2
XP
.S
B.

Sample Output

1.2
1.7

• 代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
char a[22][22];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int n,m,x,y,xx,yy,flag;
double ans[22][22][2]; //到x，y点，有加速或无加速时最短的时间,最后再比较到目的点两种方式的最短时间
struct node
{
    int x,y;
    int s;
    double sec;
};
void BFS()
{
    node now,next;
    queue<node>q;
    now.x=x;
    now.y=y;
    now.s=0;
    now.sec=0.0;
    q.push(now);
    ans[now.x][now.y][now.s]=now.sec;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.x==xx||now.y==yy)
        {
            flag=1;
            for(int i=min(now.x,xx);i<=max(now.x,xx);i++)
            {
                for(int j=min(now.y,yy);j<=max(now.y,yy);j++)
                {
                    if(a[i][j]=='X')
                    {
                        flag=0;
                        break;
                    }
                }
            }
            if(flag==1)
            ans[xx][yy][now.s]=min(ans[xx][yy][now.s],now.sec+0.2*(abs(now.x-xx)+abs(now.y-yy)));
        }
        for(int i=0;i<4;i++)
        {
            next=now;
            next.x+=dir[i][0];
            next.y+=dir[i][1];
            if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&a[next.x][next.y]!='X')
            {
                if(now.s==0)
                    next.sec+=1.0;
                if(now.s==1)
                    next.sec+=0.5;
                if(a[next.x][next.y]=='S')
                    next.s=1;
                else
                {
                    if(now.s==0)
                        next.s=0;
                    else
                        next.s=1;
                }if(ans[next.x][next.y][next.s]>next.sec)
            {
                ans[next.x][next.y][next.s]=next.sec;
                q.push(next);
            }
            }
        }
    }
}
int main()
{
    int i,j,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<22;i++)
            for(j=0;j<22;j++)
                for(k=0;k<2;k++)
                ans[i][j][k]=999999.0;
        memset(a,0,sizeof(a));
        for(i=0;i<n;i++)
            scanf("%s",a[i]);
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(a[i][j]=='P')
                {
                    x=i;
                    y=j;
                }
                if(a[i][j]=='B')
                {
                    xx=i;
                    yy=j;
                }
            }
        }
        BFS();
        double aa=min(ans[xx][yy][0],ans[xx][yy][1]);
        if(aa==999999.0) //说明这一点并没有被经过
            printf("-1");
        else
            printf("%.1f\n",min(ans[xx][yy][0],ans[xx][yy][1]));
    }
    return 0;
}