有一个推箱子的游戏, 一开始的情况如下图: 上图中, ‘.’ 表示可到达的位置, ‘#’ 表示不可到达的位置,其中 S 表示你起始的位置 , 0表示初始箱子的位置 , E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格; ..S0.. -> …S0. 注意不能将箱子推动到’#’上, 也不能将箱子推出边界; 现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成 , 则输出-1。-笔试面试资料

这是qklbishe.com第6285 篇笔试面试资料
提供答案分析,通过本文《有一个推箱子的游戏, 一开始的情况如下图:
上图中, ‘.’ 表示可到达的位置, ‘#’ 表示不可到达的位置,其中 S 表示你起始的位置 , 0表示初始箱子的位置 , E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格; ..S0.. -> …S0. 注意不能将箱子推动到’#’上, 也不能将箱子推出边界; 现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成 , 则输出-1。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

有一个推箱子的游戏, 一开始的情况如下图:
有一个推箱子的游戏, 一开始的情况如下图:          上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置 , 0表示初始箱子的位置 , E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;       ..S0.. -> ...S0.       注意不能将箱子推动到'#'上, 也不能将箱子推出边界;       现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成 , 则输出-1。
上图中, ‘.’ 表示可到达的位置, ‘#’ 表示不可到达的位置,其中 S 表示你起始的位置, 0表示初始箱子的位置, E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;

..S0.. -> …S0.

注意不能将箱子推动到’#’上, 也不能将箱子推出边界;

现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。

有一个推箱子的游戏, 一开始的情况如下图:          上图中, '.' 表示可到达的位置, '#' 表示不可到达的位置,其中 S 表示你起始的位置 , 0表示初始箱子的位置 , E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格;       ..S0.. -> ...S0.       注意不能将箱子推动到'#'上, 也不能将箱子推出边界;       现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成 , 则输出-1。 零葬
bfs穷举所有的情况,需要注意的是:人到了箱子的上下左右位置才能推动箱子一起走,否则只是人走箱子不走
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;  public class Main {     public static void main(String[] args){         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int m = sc.nextInt();         char[][] chars = new char[n][m];         // 人的起始位置S以及箱子的位置         int startX = 0, startY = 0, boxX = 0, boxY = 0;         // 判断位置,即人要先找到箱子,再推着箱子往前走         for(int i = 0;i < n;i++){                String string = sc.next();             for(int j = 0; j < m; j++){                 chars[i][j] = string.charAt(j);                 if(chars[i][j] == 'S'){                     // 人开始的位置                     startX = i;                     startY = j;                 }                 if(chars[i][j] == '0'){                     // 箱子的位置                     boxX = i;                     boxY = j;                 }             }         }         System.out.println(bfs(chars, startX, startY, boxX, boxY));     }      private static int bfs(char[][] chars, int startX, int startY, int boxX, int boxY) {         Node start = new Node(startX, startY, boxX, boxY);         int n = chars.length;         int m = chars[0].length;         // iswalked四维数组,可以用来存储走过的路径以防重复。         int[][][][] iswalked = new int[n][m][n][m];         // 每个节点都有dir4个方向的移动,分别是下右上左         int[][] movedir = new int[][]{{1, 0},{0, 1},{-1, 0},{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 + movedir[i][1] == cur.by){                          newBy = cur.by + movedir[i][1];                      }else{                          newBy = cur.by;                      }                 }                 if(cur.py == cur.by){                     if(cur.px + movedir[i][0] == cur.bx){                         newBx = cur.bx + movedir[i][0];                     }else{                         newBx = cur.bx;                     }                }                 // 箱子找到了要随人往4个方向动;没找到则箱子不动人动                 Node next = new Node(cur.px + movedir[i][0], cur.py + movedir[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                    || chars[next.px][next.py] == '#'                    || chars[next.bx][next.by] == '#'){                     continue;                 }                 // 0说明这条路径没有走过                 if(iswalked[next.px][next.py][next.bx][next.by] == 0){                     iswalked[next.px][next.py][next.bx][next.by] = 1;                     next.step = cur.step + 1;                     if(chars[next.bx][next.by] == 'E'){                         // 此时把箱子推到终点了                         return next.step;  // 最先到终点的就是最短路径                     }                     queue.offer(next);                 }             }         }         return -1;     }          public 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;         }     } }

今天 15:10:37 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 有一个推箱子的游戏, 一开始的情况如下图: 上图中, ‘.’ 表示可到达的位置, ‘#’ 表示不可到达的位置,其中 S 表示你起始的位置 , 0表示初始箱子的位置 , E表示预期箱子的位置,你可以走到箱子的上下左右任意一侧, 将箱子向另一侧推动。如下图将箱子向右推动一格; ..S0.. -> …S0. 注意不能将箱子推动到’#’上, 也不能将箱子推出边界; 现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成 , 则输出-1。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情