909. 蛇梯棋

1. 题目

给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，从左下角开始 （即，从 board[n - 1][0] 开始）每一行交替方向。

玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。

每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

  • 选定目标方格next，目标方格的编号符合范围 [curr + 1, min(curr + 6, n2)]
    • 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
  • 传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。
  • 当玩家到达编号 n2 的方格时，游戏结束。

r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格上没有蛇或梯子。

注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。

  • 举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但 不能 顺着方格 3 上的梯子前往方格 4 。

返回达到编号为 n2 的方格所需的最少移动次数，如果不可能，则返回 -1。

示例 1：

img

1
2
3
4
5
6
7
8
9
输入：board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
输出：4
解释：
首先，从方格 1 [第 5 行，第 0 列] 开始。 
先决定移动到方格 2 ，并必须爬过梯子移动到到方格 15 。
然后决定移动到方格 17 [第 3 行，第 4 列]，必须爬过蛇到方格 13 。
接着决定移动到方格 14 ，且必须通过梯子移动到方格 35 。 
最后决定移动到方格 36 , 游戏结束。 
可以证明需要至少 4 次移动才能到达最后一个方格，所以答案是 4 。

示例 2：

1
2
输入：board = [[-1,-1],[-1,3]]
输出：1

提示：

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • grid[i][j] 的值是 -1 或在范围 [1, n2] 内
  • 编号为 1 和 n2 的方格上没有蛇或梯子

2. 思路

  • 已知题目要求从左下角到左上角的最小路径，同时整个棋盘呈现的是二维数组
  • 首先将二维数组的棋盘转化为一维数组，完成转化后对应初始化双端队列（广度搜索用队列，深度搜索用递归）
  • 广度搜索比较适合用于求解最优问题的解，比如最短路径、最少次数，但也由于这种策略盲目性比较大，占用空间则需要队列，而深度搜索则适用于所有问题，只需要保存起始状态和路径上的节点
  • 初始化完队列后，同步构建出访问数组，用于标记哪个节点已经被访问过，防止重复访问
  • 将左下角第一个节点推入队列中，同时改变其标记位，并初始化结果变量result为0
  • 遍历层次提取出队列中存在的节点值，每一层相当于一次选择，因为题目中提到了next索引存在着6种取值，同时遍历完每一层后对应的需要将结果变量进行+1
  • 遍历的过程中，需要计算出对应的下一个遍历坐标，并判断该坐标是否为最后一个坐标，如果为最后一个坐标，则直接返回result + 1作为最小步数
  • 下一个坐标的计算过程中，对应需要判断是否为蛇或梯子（即判断值是否为-1），如果为蛇或梯子则下一个坐标直接替换为对应的下标值
  • 计算下一个坐标的过程中，将下一个坐标存储至队列中，同时标记访问数组为1
  • 如果队列已为空，则表示无法从该有向图中的左下角按照规则访问至左上角，返回-1

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public int snakesAndLadders(int[][] board) {
        var length = board.length;
        var nums = new int[length * length + 1];
        var queue = new ArrayDeque<Integer>();

        var rightFirst = true;
        var idx = 1;
        for (var i = length - 1; i >= 0; --i) {
            if (rightFirst) {
                for (var j = 0; j < length; ++j) {
                    nums[idx++] = board[i][j];
                }
            } else {
                for (var j = length - 1; j >= 0; --j) {
                    nums[idx++] = board[i][j];
                }
            }
            
            rightFirst = !rightFirst;
        }

        queue.offer(1);
        var visit = new int[length * length + 1];
        var result = 0;
        visit[1] = 1;

        while (!queue.isEmpty()) {
            var size = queue.size();

            for (var i = 0; i < size; ++i) {
                var curIndex = queue.poll();

                for (var j = 1; j <= 6 && j + curIndex < nums.length; ++j) {
                    var nextIndex = nums[curIndex + j] == -1 ? curIndex + j : nums[curIndex + j];
                    if (nextIndex == nums.length - 1) {
                        return result + 1;
                    }

                    if (visit[nextIndex] != 1) {
                        visit[nextIndex] = 1;
                        queue.offer(nextIndex);
                    }
                }
            }
            result++;
        }

        return -1;
    }
}

4. 复杂度

  • 时间复杂度：O(N²)
  • 空间复杂度：O(N²)

image-20231103093820746