吃豆人

吃豆人是一款非常经典的游戏,游戏中玩家控制吃豆人在地图上吃光所有豆子,并且避免被怪物抓住。

这道题没有怪物,将游戏的画面分成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;

      }

}

发布者:songJian   点击数:270   发布时间:2017-05-23 23:28:46   更新时间:2018-04-12 16:54:29
正在加载评论...
相关文章