909. 蛇梯棋

Problem: 909. 蛇梯棋

思路

这题本来我想用dp来解，但是后来发现，本题具有后效性，不符合dp的基本要求。因为本题中的蛇可能会往回走，而往回走又可能反而更快，因此不能使用dp。

出于本题的一般性，这题更适合抽象成BFS的做法。首先我们知道，BFS是最适合用来求无权有向图的最短路径的，正好本题就可以抽象成这样的图，按照BFS来求解即可。

细节

本题用转行交替的形式编号，观察board数组，首先行被倒序了，因此我们用n - 1 - row来表示行。列编号每个一行转一个方向，因此对于偶数行，列号为n - 1 - ((next - 1) % n)，即总列数减去当前编号所”应该在“的列。

Code

[]

class Solution {
    int n;
    public int snakesAndLadders(int[][] board) {
        n = board.length;
        int end = n * n;
        Queue<Integer> q = new LinkedList<>();
        boolean[] vis = new boolean[end + 1];
        int ans = 0;
        q.offer(1);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int c = 0; c < size; c++) {
                int now = q.poll();
                if (now == end) return ans;
                for (int i = 1; i <= 6 && now + i <= end; i++) {
                    int next = now + i;
                    int row = (next - 1) / n;
                    int col = row % 2 == 1 ? n - 1 - ((next - 1) % n) : (next - 1) % n;
                    row = n - 1 - row;
                    int teleport = board[row][col];
                    if (teleport != - 1) next = teleport;
                    if (!vis[next]){
                        q.offer(next);
                        vis[next] = true;
                    }
                }
            }
            ans++;
        }
        return -1;
    }
}