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%的用户