[LeetCode] 909. Snakes and Ladders

[grandyang]

On an N x N board, the numbers from 1 to N*Nare written boustrophedonically starting from the bottom left of the board, and alternating direction each row.  For example, for a 6 x 6 board, the numbers are written as follows:

You start on square 1 of the board (which is always in the last row and first column).  Each move, starting from square x, consists of the following:

• You choose a destination square S with number x+1, x+2, x+3, x+4, x+5, or x+6, provided this number is <= N*N.
  • (This choice simulates the result of a standard 6-sided die roll: ie., there are always at most 6 destinations, regardless of the size of the board.)
• If S has a snake or ladder, you move to the destination of that snake or ladder.  Otherwise, you move to S.

A board square on row r and column c has a "snake or ladder" if board[r][c] != -1.  The destination of that snake or ladder is board[r][c].

Note that you only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving.  (For example, if the board is [[4,-1],[-1,3]], and on the first move your destination square is 2, then you finish your first move at 3, because you do notcontinue moving to 4.)

Return the least number of moves required to reach square N*N.  If it is not possible, return -1.

Example 1:

Input: [
[-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]]
Output: 4
Explanation:
At the beginning, you start at square 1 [at row 5, column 0].
You decide to move to square 2, and must take the ladder to square 15.
You then decide to move to square 17 (row 3, column 5), and must take the snake to square 13.
You then decide to move to square 14, and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
It can be shown that you need at least 4 moves to reach the N*N-th square, so the answer is 4.

Note:

1. 2 <= board.length = board[0].length <= 20
2. board[i][j] is between 1 and N*N or is equal to -1.
3. The board square with number 1 has no snake or ladder.
4. The board square with number N*N has no snake or ladder.

这道题给了一个 NxN 大小的二维数组，从左下角从1开始，蛇形游走，到左上角或者右上角到数字为 NxN，中间某些位置会有梯子，就如同传送门一样，直接可以到达另外一个位置。现在就如同玩大富翁 Big Rich Man 一样，有一个骰子，可以走1到6内的任意一个数字，现在奢侈一把，有无限个遥控骰子，每次都可以走1到6以内指定的步数，问最小能用几步快速到达终点 NxN 位置。博主刚开始做这道题的时候，看是求极值，以为是一道动态规划 Dynamic Programming 的题，结果发现木有办法重现子问题，没法写出状态转移方程，只得作罢。但其实博主忽略了一点，求最小值还有一大神器，广度优先搜索 BFS，最直接的应用就是在迷宫遍历的问题中，求从起点到终点的最少步数，也可以用在更 general 的场景，只要是存在确定的状态转移的方式，可能也可以使用。这道题基本就是类似迷宫遍历的问题，可以走的1到6步可以当作六个方向，这样就可以看作是一个迷宫了，唯一要特殊处理的就是遇见梯子的情况，要跳到另一个位置。这道题还有另一个难点，就是数字标号和数组的二维坐标的转换，这里起始点是在二维数组的左下角，且是1，而代码中定义的二维数组的 (0, 0) 点是在左上角，需要转换一下，还有就是这道题的数字是蛇形环绕的，即当行号是奇数的时候，是从右往左遍历的，转换的时候要注意一下。

难点基本都提到了，现在开始写代码吧，既然是 BFS，就需要用队列 queue 来辅助，初始时将数字1放入，然后还需要一个 visited 数组，大小为 nxn+1。在 while 循环中进行层序遍历，取出队首数字，判断若等于 nxn 直接返回结果 res。否则就要遍历1到6内的所有数字i，则 num+i 就是下一步要走的距离，需要将其转为数组的二维坐标位置，这个操作放到一个单独的子函数中，后边再讲。有了数组的坐标，就可以看该位置上是否有梯子，有的话，需要换成梯子能到达的位置，没有的话还是用 num+i。有了下一个位置，再看 visited 中的值，若已经访问过了直接跳过，否则标记为 true，并且加入队列 queue 中即可，若 while 循环退出了，表示无法到达终点，返回 -1。将数字标号转为二维坐标位置的子函数也不算难，首先应将数字标号减1，因为这里是从1开始的，而代码中的二维坐标是从0开始的，然后除以n得到横坐标，对n取余得到纵坐标。但这里得到的横纵坐标都还不是正确的，因为前面说了数字标记是蛇形环绕的，当行号是奇数的时候，列数需要翻转一下，即用 n-1 减去当前列数。又因为代码中的二维数组起点位置在左上角，同样需要翻转一样，这样得到的才是正确的横纵坐标，返回即可，参见代码如下：

解法一：

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size(), res = 0;
        queue<int> q{{1}};
        vector<bool> visited(n * n + 1);
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                int num = q.front(); q.pop();
                if (num == n * n) return res;
                for (int i = 1; i <= 6 && num + i <= n * n; ++i) {
                    auto pos = getPosition(num + i, n);
                    int next = board[pos[0]][pos[1]] == -1 ? (num + i) : board[pos[0]][pos[1]];
                    if (visited[next]) continue;
                    visited[next] = true;
                    q.push(next);
                }
            }
            ++res;
        }
        return -1;
    }
    vector<int> getPosition(int num, int n) {
        int x = (num - 1) / n, y = (num - 1) % n;
        if (x % 2 == 1) y = n - 1 - y;
        x = n - 1 - x;
        return {x, y};
    }
};

我们也可以让子函数直接返回正确的数字标号，而不是数组的二维坐标，这样的写法虽然解题思路和上面都一样，但击败率要更高一些，参见代码如下：
解法二：

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size(), res = 0;
        queue<int> q{{1}};
        vector<bool> visited(n * n + 1);
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                int num = q.front(); q.pop();
                if (num == n * n) return res;
                for (int i = 1; i <= 6 && num + i <= n * n; ++i) {
                    int next = getBoardValue(board, num + i);
                    if (next == -1) next = num + i;
                    if (visited[next]) continue;
                    visited[next] = true;
                    q.push(next);
                }
            }
            ++res;
        }
        return -1;
    }
    int getBoardValue(vector<vector<int>>& board, int num) {
        int n = board.size(), x = (num - 1) / n, y = (num - 1) % n;
        if (x % 2 == 1) y = n - 1 - y;
        x = n - 1 - x;
        return board[x][y];
    }
};

Github 同步地址:

#909

参考资料：

https://leetcode.com/problems/snakes-and-ladders/

https://leetcode.com/problems/snakes-and-ladders/discuss/174643/C%2B%2B-solutions-Easy-to-understandBFS

https://leetcode.com/problems/snakes-and-ladders/discuss/173682/Java-concise-solution-easy-to-understand

LeetCode All in One 题目讲解汇总(持续更新中...)