# 909 -「java」一维数组展开+ BFS解决 -蛇梯棋- 最短步进次数 的详细思路

Tags:

• 中等

• 数组

• BFS

• java

题目链接:

909. 蛇梯棋

注意事项 [题目中的坑]:

1. 【"S形"的概念】: 题目开头举例的N*N的数组, 其内标示的1~N²数字, 指代的是当前格子是第几个格子, 用于标识S形路径的路线图, 并不是指当前格子内的元素值;

2. 【"梯子"/"蛇"的概念】: 题目开头示例图中的"梯子"/"蛇"示例, 是需要匹配示例给的示例输入数组去看, 示例的二维数组中bord5为15, 此处为一个"梯子", 其元素值为"15", 其出口为"第15个方格", 出口坐标位置bord3; 从bord3位置的下一步, 可以走到bord3, 此处为"蛇", 元素值为"13", 则其出口为"第13个格子", 出口坐标位置为bord3....

3. 【"前进"的注意事项】: 本题中的"前进", 是指"步进", 步进的过程只可往前, 不可向后(即只能顺着以为数组的角标向后遍历), 除非是步进后直接走到了"梯子"/"蛇"处, 才有可能会走回头路; 所以为了避免此时回头路出现死循环的状况, 则需要利用Map做缓存, 存储在指定一维角标处, 已经走的步数;

解题思路 [数组展开 + BFS]:

1. 因为题目中输入为二维数组, 且要求遍历路径为S形, "梯子"和"蛇"的出口是按照方格的个数标记, 所以, 可以想到先将原二维数组按照题目的要求S形一维展开;

2. 根据题目意思, 可以简化模型为: 操作一维数组, 每次步进距离为[1~6], 步进后遇到"梯子"/"蛇"的位置, 即直接跳到"梯子"/"蛇"的出口, 判断一共需要几次能跳到一维数组的尾部;

3. 根据简化后的模型判断此题为"几步内走道指定位置"的求解题, 此类型题目可以使用BFS求解;

4. 利用队列, 队列中存储的是当前步进位置的角标, 队列中拉取元素, 判断下一步能够走到的所有途径放入到队列中, 遍历的终止条件为, 当前遍历位置/下一步能够达到一维数组的尾部, 直至队列为空再停止遍历;

实现代码 [java]:

 class Solution {
     public int snakesAndLadders(int[][] board) {
         //二维数组先展开成一维
         int l = board.length;
         int w = board[0].length;
         int[] temp = new int[l*w];
         for(int i = 0; i< l; i++){
             int curr= w * i;
             boolean isRight = (i%2 == 0);
             for(int j = 0; j< w; j++){
                 if(isRight){//从左往右遍历单行
                     temp[curr +j] = board[l-i-1][j];
                 }else{//从右往左遍历当行
                     temp[curr +j] = board[l-i-1][w-j-1];
                 }
             }
         }
 ​
         //广度优先算法(借助队列实现)
         Queue<Integer> queue = new LinkedList<>();  //存储从当前节点能够走出的所有情况的(一维展开数组的)角标
         Map<Integer, Integer> m= new HashMap<>();   //key: 当前个格子数, value: 当前格子下, 已经走的步数
         queue.add(0);
         m.put(0,0);
 ​
         while(!queue.isEmpty()){
             int s = queue.size();
             for(int i=0; i< s; i++){
                 Integer curr = queue.poll();
                 int step = m.get(curr);
                 if(curr == l*w) return step;
 ​
                 for(int j = 1; j<=6; j++){
                     int np = curr+j;
                     if(np <=0 || np > l*w) continue;
                     if(temp[np] != -1){   //梯子或蛇
                         np = temp[np]-1; //此处注意: 是移动到第15个, 而不是temp[15]
                     }
                     if(np +1 == l*w) return step+1; //单次跳跃, 直接跳到终点
                     if(m.containsKey(np)) continue;
                     queue.add(np);
                     m.put(np, step+1);
                 }
             }
         }
         return -1;
     }
 }

提交记录 [20210627]:

 执行用时：7 ms, 在所有 Java 提交中击败了66.90%的用户
 内存消耗：38.4 MB, 在所有 Java 提交中击败了83.80%的用户