吃豆人
吃豆人是一款非常经典的游戏，游戏中玩家控制吃豆人在地图上吃光所有豆子，并且避免被怪物抓住。
这道题没有怪物，将游戏的画面分成n*m的格子，每格地形可能为空地或者障碍物，吃豆人可以在空地上移动，吃豆人每移动一格需要1s时间，并且只能朝上下左右四个方向移动，特别的是吃豆人还能吐出舌头，舌头每移动一格需要0.1s时间，舌头只可以走直线。不必考虑吃豆人转身所需要的时间。
举例，吃豆人在(1,1)坐标，而豆子在(1,5)坐标，并且中间没有障碍物，此时朝豆子方向吐舌头～，经过0.8s就可以吃到豆子(来回各0.4s,吐出去的舌头要缩回来的嘛)。
游戏中还有加速道具，一旦得到加速道具，吃豆人就获得2倍移动速度，吐舌头的速度没有增加，即走1格用0.5s。现在地图上有且只有一颗豆子。游戏中有.代表空地；X表示障碍，吃豆人不能越过障碍；B代表豆子；S代表加速道具，并且地图上道具总数不超过1个，道具所在的位置为空地，得到道具后立即使用，道具立即消失，地形变为空地，不能用舌头去取道具；P表示吃豆人,吐舌头的时候吃豆人不能移动。
解：
public class chiDou {
// 复制地图
public static String[][] copy(String[][] vv) {
String[][] xxx = new String[n + 2][m + 2];
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < m + 2; j++) {
xxx[i][j] = vv[i][j];
}
}
return xxx;
}
// 加上外围
public static void body(int n, int m) {
for (int i = 0; i < m + 2; i++) {
xx[0][i] = "x";
xx[n + 1][i] = "x";
}
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < 2; j++) {
xx[i][0] = "x";
xx[i][m + 1] = "x";
}
}
}
// 显示地图
public static void show(int n, int m) {
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < m + 2; j++) {
System.out.print(xx[i][j]);
}
System.out.println();
}
}
// 地图
static String[][] xx;
// 坐标和地图大小
static int px, py, bx, by, ca, n, m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
xx = new String[n + 2][m + 2];
// 因为到时候外面要加一层障碍物,所以从1开始
for (int i = 1; i < n + 1; i++) {
String xi = sc.next();
char[] xic = xi.toCharArray();
for (int k = 1; k < xic.length + 1; k++) {
xx[i][k] = String.valueOf(xic[k - 1]);
if (xx[i][k].equals("p")) {
px = i;
py = k;
}
if (xx[i][k].equals("b")) {
bx = i;
by = k;
}
}
}
// 加上外边
body(n, m);
// 用于保存最小时间
min = Double.MAX_VALUE;
// 显示地图
// show(n, m);
// 搜索
gogo(xx, px, py, 0);
System.out.println(min);
}
static double min;
// 递归搜寻路线
public static void gogo(String[][] xx, int x, int y, double time) {
String[][] xxx = copy(xx);
// 如果吃到加速，时间减去一半
if (xxx[x][y].equals("s")) {
time -= 0.5;
}
// 判断是否可以吃到豆子
cg(x, y, time);
// 封住回路
xxx[x][y] = "x";
// 寻找可以走的方向，递归搜寻（深度优先）
if (xxx[x - 1][y].equals(".") || xxx[x - 1][y].equals("s")) {
gogo(xxx, x - 1, y, time + 1);
}
if (xxx[x + 1][y].equals(".") || xxx[x + 1][y].equals("s")) {
gogo(xxx, x + 1, y, time + 1);
}
if (xxx[x][y - 1].equals(".") || xxx[x][y - 1].equals("s")) {
gogo(xxx, x, y - 1, time + 1);
}
if (xxx[x][y + 1].equals(".") || xxx[x][y + 1].equals("s")) {
gogo(xxx, x, y + 1, time + 1);
}
}
// 可不可以吃到豆子
public static void cg(int x, int y, double time) {
if ((x == bx || y == by) && bb(x, y, bx, by)) {
ca = (x - bx) + (y - by);
if (ca < 0) {
ca = -ca;
}
time += ca * 0.2;
if (time < min) {
min = time;
}
}
}
// 坐标平了之后，判断其中间是否有障碍物
public static boolean bb(int a, int b, int c, int d) {
if (a > b) {
int e = a;
a = b;
b = e;
}
if (c > d) {
int e = c;
c = d;
d = e;
}
if (a == c) {
for (int i = b; i < d; i++) {
if (xx[a][i].equals("x")) {
return false;
}
}
} else {
for (int i = a; i < c; i++) {
if (xx[i][b].equals("x")) {
return false;
}
}
}
return true;
}
}