给定一个蛇梯棋盘，计算 出到达目的地或从源地或第一个格子到最后一个格子所需的最少掷骰次数。基本上，玩家完全掌控掷骰结果，并想知道达到最后一个格子所需的最少掷骰次数。
如果玩家到达一个格子，那是梯子的底部，玩家必须爬上梯子;如果到达一个格子是蛇的嘴巴，必须不掷骰子就下到蛇的尾巴。
示例：
输入：
输出：3
说明：步骤如下：
先掷两颗骰子达到3号格子，然后用梯子掷到22号
然后掷6个，达到28个。
最后通过2到30。
还可以有其他解，比如（2， 2， 6）， （2， 4， 4）， （2， 3， 5）..等等。
[接近 - 1]使用广度优先搜索——时间和空间为O（n）
这个想法是把蛇梯棋盘建模成一个图，每个单元格是一个节点，掷骰子代表边。我们的想法是使用广度优先搜索（BFS），因为我们寻找从头到尾的最短路径（最小移动次数）。一个重要的观察是，当你用梯子或蛇落在一个格子上时，你会被传送到一个新的格子，这实际上改变了该边的目的地节点。BFS会以最短的先掷方式探索每个格子的所有可能掷骰，确保我们以最少的掷骰次数到达最终格子。
实施上述理念的步骤：
创建一个访问过的数组，以跟踪在BFS遍历板块期间访问过的格子。
初始化一个 队列，存储当前单元索引对和已移动次数。
从0单元格开始 ，距离为0，标记已访问，并推入队列作为起点。
当队列不是空的，提取前端元素，获取当前单元和距离。
如果当前格子是最后一个，返回距离，因为它代表最小掷骰次数。
用掷骰子循环所有可能的6个格子，每个格子都要检查蛇跳或梯子跳。
如果目标单元格未被访问，标记其已访问，并以距离递增1的顺序排队。
// Java program to find minimum number of dice throws // in Snakes and Ladders using BFS import java.util.*; class GfG { // Function to find the minimum number of dice throws static int getMinDiceThrows(int[] move) { int n = move.length; boolean[] visited = new boolean[n]; Queue<int[]> q = new LinkedList<>(); visited[0] = true; // Start from cell 0 with 0 moves q.add(new int[]{0, 0}); while (!q.isEmpty()) { int[] curr = q.peek(); int v = curr[0]; int dist = curr[1]; if (v == n - 1) return dist; q.remove(); // Try all possible dice throws from current cell for (int j = v + 1; j <= v + 6 && j < n; ++j) { if (!visited[j]) { visited[j] = true; // Move to destination cell if // there's a ladder/snake int dest = (move[j] != -1) ? move[j] : j; q.add(new int[]{dest, dist + 1}); } } } return -1; } public static void main(String[] args) { int n = 30; int[] moves = new int[n]; Arrays.fill(moves, -1); // Ladders moves[2] = 21; moves[4] = 7; moves[10] = 25; moves[19] = 28; // Snakes moves[26] = 0; moves[20] = 8; moves[16] = 3; moves[18] = 6; System.out.println(getMinDiceThrows(moves)); } }输出
3
[接近 - 2]使用深度优先搜索——时间为O（n），空间为O（n）
其理念是利用深度优先搜索（DFS）模拟所有可能的骰子掷出， 从头到尾探索每一条路径。思路是从当前位置移动到所有可能的下一个位置（通过掷骰1–6），如果有蛇或梯子就跳到新位置。一个重要的观察是利用已访问的地图，跟踪每个格子的最小移动，修剪已经比之前发现路径更差的路径。这样我们只追求最优路径，当找到更短路径时就提前停止。
实施上述理念的步骤：
定义一个递归函数，用移动计数器探索当前局面的所有可能路径。
使用地图追踪已访问位置及到达每个位置所需的最少步数。
添加一个基准情况，以便在当前路径到达最终目的地时更新最小移动数。
如果当前路径需要比同一局面已有的走法更多的走法，则修剪递归。
每次叫注时，模拟所有掷骰子从1到6的掷骰结果，并相应计算下一局面。
如果下一个单元格有梯形或蛇形，先跳到目的地再进行递归调用。
从位置0开始函数， 如果没有有效路径到达电路板末端，则返回-1。
// Java program to find minimum number of dice throws // in Snakes and Ladders using DFS import java.util.*; class GfG { // Recursive DFS to explore all paths from current position static void dfs(int currPos, int movesMade, int[] move, Map<Integer, Integer> visited, int n, int[] res) { // Prune paths that are worse than already found or visited if (movesMade >= res[0] || (visited.containsKey(currPos) && movesMade >= visited.get(currPos))) { return; } // Reached the last cell, update result if (currPos == n - 1) { res[0] = movesMade; return; } visited.put(currPos, movesMade); // Explore all dice throws (1 to 6) for (int i = 1; i <= 6 && currPos + i < n; ++i) { int nextPos = currPos + i; // Jump if ladder/snake present int dest = (move[nextPos] != -1) ? move[nextPos] : nextPos; dfs(dest, movesMade + 1, move, visited, n, res); } } // Function to find the minimum number of dice throws static int getMinDiceThrows(int[] move) { int n = move.length; Map<Integer, Integer> visited = new HashMap<>(); int[] res = {Integer.MAX_VALUE}; // Start DFS from cell 0 dfs(0, 0, move, visited, n, res); return (res[0] == Integer.MAX_VALUE) ? -1 : res[0]; } public static void main(String[] args) { int n = 30; int[] moves = new int[n]; Arrays.fill(moves, -1); // Ladders moves[2] = 21; moves[4] = 7; moves[10] = 25; moves[19] = 28; // Snakes moves[26] = 0; moves[20] = 8; moves[16] = 3; moves[18] = 6; System.out.println(getMinDiceThrows(moves)); } }输出
3
编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548
