本文共 6021 字，大约阅读时间需要 20 分钟。
1、
2、
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
Sample Input
2 2XPB.3 2XP.SB.
Sample Output
1.21.7
参考网上ＡＣ代码：
#includeAC代码：#include #include #include using namespace std;#define INF 100000#include char map[25][25];int sx,sy,bx,by,px,py,n,m;double tg[25][25];int dir[4][2]={0,1,1,0,-1,0,0,-1};int visit[25][25];struct node{ int x; int y; double t;}a[500];//处理舌头的时候注意分别向两端处理void init() { //处理与豆在同一行或者同一列的格子 memset(tg, 0, sizeof(tg)); for (int i = bx + 1; i <=n; i++) { if (map[i][by] != 'X') tg[i][by] = (i - bx) * 0.2; else break; } for (int i = bx - 1; i > 0; i--) { if (map[i][by] != 'X') tg[i][by] = (bx - i) * 0.2; else break; } for (int i = by + 1; i <= m; i++) { if (map[bx][i] != 'X') tg[bx][i] = (i - by) * 0.2; else break; } for (int i = by - 1; i > 0; i--) { if (map[bx][i] != 'X') tg[bx][i] = (by - i) * 0.2; else break; }}double bfs(int Sx,int Sy,char e,double time){ memset(visit,0,sizeof(visit)); int front=0,rear=1; a[0].x=Sx; a[0].y=Sy; a[0].t=0; visit[Sx][Sy]=1; double ans=INF; while(front<=rear) { node cur=a[front++]; if(map[cur.x][cur.y]==e) ans=min(ans,cur.t); else if(e=='B' && tg[cur.x][cur.y]!=0) ans=min(ans,cur.t+tg[cur.x][cur.y]); for(int i=0;i<4;i++) { int tx=cur.x+dir[i][0]; int ty=cur.y+dir[i][1]; if(tx>=1 && tx<=n && ty>=1 && ty<=m && map[tx][ty]!='X' && visit[tx][ty]==0) { visit[tx][ty]=1; node tmp; tmp.x=tx; tmp.y=ty; tmp.t=cur.t+time; a[rear++]=tmp; } } } return ans;}queue que;double bfs1(int x, int y, char end, double time) { //(x,y)为起点，end为结束点，t为走一步花的时间 while (!que.empty()) { que.pop(); } memset(visit, 0, sizeof(visit)); double ans=10000; node first; first.x = x, first.y = y, first.t = 0; que.push(first); visit[x][y] = true; while (!que.empty()) { first = que.front(); que.pop(); if (map[first.x][first.y] == end) { ans = min(ans, first.t); } else if (end == 'B' && tg[first.x][first.y] != 0) { ans = min(ans, first.t + tg[first.x][first.y]); } for (int i = 0; i < 4; i++) { int xx = first.x + dir[i][0], yy = first.y + dir[i][1]; if (xx>=1 && xx<=n && yy>=1 && yy<=m && map[xx][yy] != 'X' && !visit[xx][yy]) { node tmp; tmp.x = xx; tmp.y = yy; tmp.t = first.t + time; que.push(tmp); visit[xx][yy] = 1; } } } return ans;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { getchar(); int px=py=sx=sy=bx=by=-1; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { scanf("%c",&map[i][j]); if(map[i][j]=='S') { sx=i; sy=j; } if(map[i][j]=='B') { bx=i; by=j; } if(map[i][j]=='P') { px=i; py=j; } } getchar(); } init(); double ans1=INF,ans2=INF,ans3=INF; //printf("*%d %d\n",px,py); ans1=bfs(px,py,'S',1); //printf("ans1=%lf\n",ans1); if(ans1!=INF) ans2=bfs(sx,sy,'B',0.5); if(ans2!=INF) ans1+=ans2; else ans1=INF; ans3=bfs(px,py,'B',1); //printf("%lf %lf %lf\n",ans1,ans2,ans3); if(ans3==INF) printf("-1\n"); else printf("%.1lf\n",min(ans1,ans3)); } return 0;}/*2 2XPB.3 2XP.SB.*/