蛇梯棋[中等]

一、题目

给你一个大小为n x n的整数矩阵board，方格按从1到n2编号，编号遵循转行交替方式，从左下角开始（即，从board[n - 1][0]开始）每一行交替方向。玩家从棋盘上的方格1（总是在最后一行、第一列）开始出发。每一回合，玩家需要从当前方格curr开始出发，按下述要求前进：
1、选定目标方格next，目标方格的编号符合范围[curr + 1, min(curr + 6, n2)]。该选择模拟了掷六面体骰子的情景，无论棋盘大小如何，玩家最多只能有6个目的地。
2、传送玩家：如果目标方格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：

输入：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：

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

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

二、代码

广度优先搜索： 我们可以将棋盘抽象成一个包含N^2个节点的有向图，对于每个节点x，若x+i (1≤i≤6)上没有蛇或梯子，则连一条从x到x+i的有向边；否则记蛇梯的目的地为y，连一条从x到y的有向边。如此转换后，原问题等价于在这张有向图上求出从1到N^2的最短路长度。

对于该问题，我们可以使用广度优先搜索。将节点编号和到达该节点的移动次数作为搜索状态，顺着该节点的出边扩展新状态，直至到达终点N^2，返回此时的移动次数。若无法到达终点则返回−1。

代码实现时，我们可以用一个队列来存储搜索状态，初始时将起点状态(1,0)加入队列，表示当前位于起点1，移动次数为0。然后不断取出队首，每次取出队首元素时扩展新状态，即遍历该节点的出边，若出边对应节点未被访问，则将该节点和移动次数加一的结果作为新状态，加入队列。如此循环直至到达终点或队列为空。

此外，我们需要计算出编号在棋盘中的对应行列，以便从board中得到目的地。设编号为id，由于每行有n个数字，其位于棋盘从下往上数的第⌊(id−1)/n⌋行，记作r。由于棋盘的每一行会交替方向，若r为偶数，则编号方向从左向右，列号为(id−1) mod n；若r为奇数，则编号方向从右向左，列号为n−1−((id−1) mod n)。

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] vis = new boolean[n * n + 1];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            for (int i = 1; i <= 6; ++i) {
                int nxt = p[0] + i;
                if (nxt > n * n) { // 超出边界
                    break;
                }
                int[] rc = id2rc(nxt, n); // 得到下一步的行列
                if (board[rc[0]][rc[1]] > 0) { // 存在蛇或梯子
                    nxt = board[rc[0]][rc[1]];
                }
                if (nxt == n * n) { // 到达终点
                    return p[1] + 1;
                }
                if (!vis[nxt]) {
                    vis[nxt] = true;
                    queue.offer(new int[]{nxt, p[1] + 1}); // 扩展新状态
                }
            }
        }
        return -1;
    }

    public int[] id2rc(int id, int n) {
        int r = (id - 1) / n, c = (id - 1) % n;
        if (r % 2 == 1) {
            c = n - 1 - c;
        }
        return new int[]{n - 1 - r, c};
    }
}