【LeetCode】909. 蛇梯棋

比眉伴天荒 2022-10-10 11:13 132阅读 0赞

> 2021.6.27力扣每日一题

### 文章目录 ###

*   *  题目链接
     *  题目简介
     *  题目解析
     *  题目代码

## 题目链接 ##

[909. 蛇梯棋][909.]

## 题目简介 ##

N x N 的棋盘 board 上，按从 1 到 N\*N 的数字给方格编号，编号 `从左下角开始`，每一行交替方向。

例如，一块 6 x 6 大小的棋盘，编号如下：

![在这里插入图片描述][55bbaddb4659bbd8f4c84d3d6f4fdfed.png_pic_center]  
r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board\[r\]\[c\] != -1，那个蛇或梯子的目的地将会是 board\[r\]\[c\]。

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

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

*  选定目标方格：选择从编号 x+1，x+2，x+3，x+4，x+5，或者 x+6 的方格中选出一个目标方格 s ，目标方格的编号 <= N\*N。
    
     *  该选择模拟了掷骰子的情景，无论棋盘大小如何，你的目的地范围也只能处于区间 \[x+1, x+6\] 之间。
 *  传送玩家：如果目标方格 S 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 S。

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

返回达到方格 N\*N 所需的最少移动次数，如果不可能，则返回 -1。

**示例：**

输入：[
    [-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 行，第 5 列]，必须爬过蛇到方格 13。
    然后你决定移动到方格 14，且必须通过梯子移动到方格 35。
    然后你决定移动到方格 36, 游戏结束。
    可以证明你需要至少 4 次移动才能到达第 N*N 个方格，所以答案是 4。

**提示：**

*  `2 <= board.length = board[0].length <= 20`
 *  board\[i\]\[j\] 介于 1 和 N\*N 之间或者等于 -1。
 *  编号为 1 的方格上没有蛇或梯子。
 *  编号为 N\*N 的方格上没有蛇或梯子。

## 题目解析 ##

1.  这个翻译真是一言难尽，实在 **`啥也看不懂`**~
2.  简单来说：给你一个图，图上每个点有自己的编号ID（蛇形分布），从 `1` ~ `n * n`，每一次你最多能走1~6个点（骰子），当你走到的点的数值不为 `-1` 时，则可以触发传送机制 **`（一次操作只能触发一次传送）`**，直接传送至该数值的点。比如你扔骰子到第二个点，第二个点的数值为8，可直接传送至第八个点。当然，每一个点只能走一次。
3.  使用BFS（广度优先搜索）
    
     *  首先，我们将第一个点放置队列，由题意我们可知，我们还需要将当前移动的次数放置，队列中存放为：`queue.offer(new int[]{1,0};)`
     *  我们进入第一轮的骰子，可以推断中，第一轮我们可以走过的点数为：`2 ~ 7`，我们还需要检查下 `2 ~ 7` 是否可以触发传送机制，这样我们就可以尽量的走远。
     *  因为我们传送的编号ID，所以我们需要通过该 `ID` 找到 `ID` 所在的下标
     *  最后如果可以到达 `n * n`，返回次数，否则，`return -1`

## 题目代码 ##

class Solution {
        
        public int snakesAndLadders(int[][] board) {
        
            Queue<int[]> queue = new LinkedList<>();
            int n = board.length;
            boolean[] vis = new boolean[n * n + 1];
            // 在第一个坐标，移动0个距离
            queue.offer(new int[]{
        1, 0});
    
            while(!queue.isEmpty()){
        
                int[] p = queue.poll();
                for(int i = 1; i <= 6; i++){
        
                	// 骰子可以移动的点数
                    int cnt = p[0] + i;
                    // 当前点数大于矩阵的最大点数
                    if(cnt > n * n){
        
                        break;
                    }
    				// 得到该点数的坐标值
                    int[] rc = id2rc(cnt, n);
    
                    // 判断这是否是个梯子，可以传送
                    if(board[rc[0]][rc[1]] > 0){
        
                    	// 是的话，可以直接进行传送操作
                        cnt = board[rc[0]][rc[1]];
                    }
    				// 正好到达终点
                    if(cnt == n * n){
        
                        return p[1] + 1;
                    }
                    
                    // 该点没有被遍历过
                    if(!vis[cnt]){
        
                        vis[cnt] = true;
                        queue.offer(new int[]{
        cnt, p[1] + 1});
                    }
                }
            }
            return
        }
    
        public int[] id2rc(int id, int n){
        
            int r = (id - 1) / n;
            int c = (id - 1) % n;
            if(r % 2 == 0){
        
                c = n - 1 - c;
            }
            return new int[]{
        n - 1 - r, c};
        }
    }

[909.]: https://leetcode-cn.com/problems/snakes-and-ladders/
[55bbaddb4659bbd8f4c84d3d6f4fdfed.png_pic_center]: /images/20221005/d58d86c0f5454a72a33d4e6d5ab8ff1a.png