题意：在一个N*M的矩阵里面，有一个吃豆人，每次可以上下左右移动，每次移动消耗1s，有些格子有障碍，矩阵中有且仅有一个豆子，吃豆人沿直线可以吐舌头吃豆，舌头伸长一格消耗0.1s，吃完还要收缩回来，收缩一个也消耗0.1s。地图中至多有一个加速器，吃了加速器以后速度变成原来的两倍，吐舌头速度不变。问到豆子至少要多久，如果吃不到输出-1。
思路：1.先考虑没有加速器的情况，因为只有一个豆子，因此可以以豆子为中心，往四个方向初始化出各个格子要吃豆子时消耗的时间。因为只要走到可吃豆的点时，走路永远没有吐舌头快（走一格1s，有加速器0.5s，而吐舌头一格来回才0.2s），所以我们只要用BFS寻找到达这些可以吃豆的点中，吃豆加移动总时间最少的解。
2.如果有加速器，那我们先算出没有加速器时的最优解，记为ans1。然后考虑吃先吃加速器的最短耗时，再计算由加速器走到可吃豆点并吃豆的最短耗时，两者加起来记为ans2，答案输出ans=min(ans1,ans2)即可。
3.可以将ans值一开始记为INF，如果求出来ans为INF，则输出-1。
就是实现起来稍微麻烦。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
char map[25][25];
bool vis[25][25],Dj;
double dist[25][25],ans,fast,pre;
int n,m,Bx,By,Sx,Sy,Djx,Djy,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void prework()//初始化每个可吃豆点吐舌头吃豆来回需要的时间
{
for(int i=0;i<n;++i)
for(int j=0;j<m;++j) dist[i][j]=INF;//初始化所有点都不可吃豆
for(int i=0;i<4;++i)
for(int x=Bx,y=By,cnt=0;x<n && y<n && x>=0 && y>=0 && map[x][y]!='X';x+=dx[i],y+=dy[i]) dist[x][y]=(cnt++)*0.2;
}
struct point{int x, y;double tim;};
bool check(point t)
{
if(t.x<0 || t.y<0 || t.x>=n || t.y>=m || vis[t.x][t.y] || map[t.x][t.y]=='X') return 0;
return 1;
}
void bfs1(point qidian)
{
memset(vis,0,sizeof(vis));
queue<point> Q;
Q.push(qidian);
while(!Q.empty())
{
point top=Q.front(); Q.pop();vis[top.x][top.y]=1;
if(dist[top.x][top.y]<INF) ans=min(ans,top.tim+dist[top.x][top.y]);
for(int i=0;i<4;++i)
{
point tmp={top.x+dx[i],top.y+dy[i],top.tim+fast};
if(check(tmp))
if(dist[tmp.x][tmp.y]<INF) ans=min(ans,tmp.tim+dist[tmp.x][tmp.y]);
else {Q.push(tmp);vis[tmp.x][tmp.y]=1;}
}
}
}
void bfs2(point qidian)
{
memset(vis,0,sizeof(vis));
queue<point> Q;
Q.push(qidian);
pre=0.0;
while(!Q.empty())
{
point top=Q.front(); Q.pop();vis[top.x][top.y]=1;
for(int i=0;i<4;++i)
{
point tmp={top.x+dx[i],top.y+dy[i],top.tim+1.0};
if(check(tmp))
if(map[tmp.x][tmp.y]=='S') {pre=tmp.tim;return;}
else {Q.push(tmp);vis[tmp.x][tmp.y]=1;}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
getchar();
for(int i=0;i<n;++i) scanf("%s",map[i]);
Dj=0,ans=INF,fast=1.0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
if(map[i][j]=='B') {Bx=i,By=j;}
else if(map[i][j]=='P') {Sx=i,Sy=j;}
else if(map[i][j]=='S') {Dj=1,Djx=i,Djy=j;}
prework();
point qd={Sx,Sy,0.0};
if(Dj==0) bfs1(qd);
else
{
bfs1(qd);
bfs2(qd);
point nqd={Djx,Djy,pre};
fast=0.5;
bfs1(nqd);
}
if(ans>=INF-5) printf("-1\n");
else printf("%.1lf\n",ans);
}
}