有一个推箱子的游戏, 一开始的情况如下图:
上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;
..S0.. -> ...S0.
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
..S0.. -> ...S0.
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);
后面为n行字符串,每行字符串有m字符, 表示游戏盘面;
一个数字,表示最少几步能完成游戏,如果不能,输出-1;
3 6 .S#..E .#.0.. ......
11
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.LinkedList; import java.util.Queue; public class Main { // 移动矩阵(上下向左右移动时,横纵坐标的改变) static int[][] move = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] temp = br.readLine().trim().split(" "); int n = Integer.parseInt(temp[0]), m = Integer.parseInt(temp[1]); char[][] maze = new char[n][]; for(int i = 0; i < n; i++) maze[i] = br.readLine().trim().toCharArray(); // 人的起始位置S以及箱子的位置 int startX = 0, startY = 0, boxX = 0, boxY = 0; // 判断位置,即人要先找到箱子,再推着箱子往前走 for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(maze[i][j] == 'S'){ // 人开始的位置 startX = i; startY = j; } if(maze[i][j] == '0'){ // 箱子的位置 boxX = i; boxY = j; } } } System.out.println(bfs(maze, startX, startY, boxX, boxY)); } private static int bfs(char[][] maze, int startX, int startY, int boxX, int boxY) { Node start = new Node(startX, startY, boxX, boxY); int n = maze.length; int m = maze[0].length; // iswalked四维数组,可以用来存储走过的路径以防重复。 int[][][][] iswalked = new int[n][n][m][m]; // 每个节点都有4个方向的移动,分别是上下左右 int[][] moveDirection = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; Queue<Node> queue = new LinkedList<>(); // 利用队列实现BFS start.step = 0; queue.offer(start); // 开始BFS广度搜索最短路径 while(!queue.isEmpty()){ Node cur = queue.poll(); int newBx = cur.bx; int newBy = cur.by; // 向4个方向走 for(int i = 0; i < 4; i++){ // 人在箱子的左右上下才能够推箱子,否则箱子的坐标不变 if(cur.px == cur.bx){ if(cur.py + moveDirection[i][1] == cur.by){ newBy = cur.by + moveDirection[i][1]; }else{ newBy = cur.by; } } if(cur.py == cur.by){ if(cur.px + moveDirection[i][0] == cur.bx){ newBx = cur.bx + moveDirection[i][0]; }else{ newBx = cur.bx; } } // 箱子找到了要随人往4个方向动;没找到则箱子不动人动 Node next = new Node(cur.px + moveDirection[i][0], cur.py + moveDirection[i][1], newBx, newBy); // 不能让人在没找到箱子之前出地图或者自己提前到目的地 if(next.px < 0 || next.px >= n || next.py < 0||next.py >= m || next.bx < 0||next.bx >= n||next.by < 0||next.by >= m || maze[next.px][next.py] == '#' || maze[next.bx][next.by] == '#'){ continue; } // 0说明这条路径没有走过 if(iswalked[next.px][next.bx][next.py][next.by] == 0){ iswalked[next.px][next.bx][next.py][next.by] = 1; next.step = cur.step + 1; if(maze[next.bx][next.by] == 'E'){ // 此时把箱子推到终点了 return next.step; // 最先到终点的就是最短路径 } queue.offer(next); } } } return -1; } private static class Node{ // 人的位置 int px; int py; // 箱子的位置 int bx; int by; // 从初始位置到现在节点所走的步数 int step; public Node(int px, int py, int bx, int by){ this.px = px; this.py = py; this.bx = bx; this.by = by; } } }