1、http://acm.fzu.edu.cn/problem.php?pid=2124
2、
D - 吃豆人
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 100000
#include <queue>
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;elsebreak;}for (int i = bx - 1; i > 0; i--) {if (map[i][by] != 'X')tg[i][by] = (bx - i) * 0.2;elsebreak;}for (int i = by + 1; i <= m; i++) {if (map[bx][i] != 'X')tg[bx][i] = (i - by) * 0.2;elsebreak;}for (int i = by - 1; i > 0; i--) {if (map[bx][i] != 'X')tg[bx][i] = (by - i) * 0.2;elsebreak;}
}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<node> 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;elseans1=INF;ans3=bfs(px,py,'B',1);//printf("%lf %lf %lf\n",ans1,ans2,ans3);if(ans3==INF)printf("-1\n");elseprintf("%.1lf\n",min(ans1,ans3));}return 0;
}
/*
2 2
XP
B.
3 2
XP
.S
B.
*/
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;#define SIZE 22struct Node {int x, y;double time;
};int n, m;
char mat[SIZE][SIZE];
bool vis[SIZE][SIZE];
double tg[SIZE][SIZE]; //记录吐舌头的速度
int Px, Py, Sx, Sy, Bx, By;
int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
queue<Node> que;void init() { //处理与豆在同一行或者同一列的格子memset(tg, 0, sizeof(tg));for (int i = Bx + 1; i < n; i++) {if (mat[i][By] != 'X')tg[i][By] = (i - Bx) * 0.2;elsebreak;}for (int i = Bx - 1; i >= 0; i--) {if (mat[i][By] != 'X')tg[i][By] = (Bx - i) * 0.2;elsebreak;}for (int i = By + 1; i < m; i++) {if (mat[Bx][i] != 'X')tg[Bx][i] = (i - By) * 0.2;elsebreak;}for (int i = By - 1; i >= 0; i--) {if (mat[Bx][i] != 'X')tg[Bx][i] = (By - i) * 0.2;elsebreak;}for(int i=0;i<n;i++)printf("*%d ",tg[i][By]);printf("\n");for(int i=0;i<m;i++)printf("&%d ",tg[Bx][i]);printf("\n");
}bool ok(int x, int y) {return x >= 0 && x < n && y >= 0 && y < m;
}double bfs(int x, int y, char end, double t) { //(x,y)为起点，end为结束点，t为走一步花的时间while (!que.empty()) {que.pop();}memset(vis, false, sizeof(vis));double ans=10000;Node first;first.x = x, first.y = y, first.time = 0;que.push(first);vis[x][y] = true;while (!que.empty()) {first = que.front();que.pop();if (mat[first.x][first.y] == end) {ans = min(ans, first.time);} else if (end == 'B' && tg[first.x][first.y] != 0) {ans = min(ans, first.time + tg[first.x][first.y]);}for (int i = 0; i < 4; i++) {int xx = first.x + dx[i], yy = first.y + dy[i];if (ok(xx, yy) && mat[xx][yy] != 'X' && !vis[xx][yy]) {Node tmp;tmp.x = xx;tmp.y = yy;tmp.time = first.time + t;que.push(tmp);vis[xx][yy] = true;}}}return ans;
}int main() {while (scanf("%d%d", &n, &m) != EOF) {Px = Py = Sx = Sy = Bx = By = -1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf(" %c", &mat[i][j]);if (mat[i][j] == 'P')Px = i, Py = j;if (mat[i][j] == 'S')Sx = i, Sy = j;if (mat[i][j] == 'B')Bx = i, By = j;}}init();printf("*%d %d\n",Px,Py);double ans1 = bfs(Px, Py, 'S', 1);double tmpans = 10000;if (ans1 != 10000) {tmpans = bfs(Sx, Sy, 'B', 0.5);}if (tmpans != 10000)ans1 += tmpans;elseans1 = 100000;double ans2 = bfs(Px, Py, 'B', 1);printf("%lf %lf %lf\n",ans1,ans2);if (ans2 == 10000)puts("-1");elseprintf("%.1lf\n", min(ans1, ans2));}
}