福州大学第十届校赛 & fzu 2124 吃豆人
思路，广搜，方案1 把加速道具当做空地忽略，从吃豆人开始 到 豆 进行广搜 。 方案2 先（以 吃豆人开始 以 加速道具结束 搜一次）加上 （以 加速道具开始 豆结束 搜一次），两种方案取最优。
wa了多次，因为 和豆 在同一行或同一列 的可以吐舌头，因此必须搜完全部路径 取最小，不能一找到就返回结果。。
#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;}}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();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);if (ans2 == 10000)puts("-1");elseprintf("%.1lf\n", min(ans1, ans2));}}