909. Snakes and Ladders

Version #1 BFS

[[1,1,-1],[1,1,1],[-1,1,1]]
[[-1,-1,2,21,-1],[16,-1,24,-1,4],[2,3,-1,-1,-1],[-1,11,23,18,-1],[-1,-1,-1,23,-1]]
[[-1,-1,-1],[-1,9,8],[-1,8,9]]
[[1,1,-1],[1,1,1],[-1,1,1]]
[[-1,-1,27,13,-1,25,-1],[-1,-1,-1,-1,-1,-1,-1],[44,-1,8,-1,-1,2,-1],[-1,30,-1,-1,-1,-1,-1],[3,-1,20,-1,46,6,-1],[-1,-1,-1,-1,-1,-1,29],[-1,29,21,33,-1,-1,-1]]
[[-1,-1,-1,46,47,-1,-1,-1],[51,-1,-1,63,-1,31,21,-1],[-1,-1,26,-1,-1,38,-1,-1],[-1,-1,11,-1,14,23,56,57],[11,-1,-1,-1,49,36,-1,48],[-1,-1,-1,33,56,-1,57,21],[-1,-1,-1,-1,-1,-1,2,-1],[-1,-1,-1,8,3,-1,6,56]]

二刷
关键是把id转换成x,y需要多加注意

33.75 %
class Solution {
    private int rows, cols;
    public int snakesAndLadders(int[][] board) {
        this.rows = board.length;
        this.cols = board[0].length;
        int maxId = rows * cols;
        if (maxId == 1) {
            return board[0][0] == -1 ? 0 : -1;
        }
        Queue<Integer> que = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        que.offer(1);
        int level = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            level++;
            while (size-- > 0) {
                int curr = que.poll();
                for (int i = 1; i <= 6; i++) {
                    int next = curr + i;
                    int[] nextPos = getPos(next);
                    if (board[nextPos[1]][nextPos[0]] != -1) {
                        next = board[nextPos[1]][nextPos[0]];
                    }
                    if (next == maxId) return level;
                    if (visited.add(next)) {
                        que.offer(next);
                    }
                }
            }
        }
        return -1;
    }
   
    private int[] getPos(int id) {
        // e.g. rows = 6, cols = 6, id = 17
        // y = 5 - 2 = 3, x = 4
        int y = rows - 1 - (id - 1) / rows;
        int x = ((id - 1) / rows) % 2 == 0  ? (id - 1) % cols : cols - 1 - (id - 1) % cols;
        return new int[]{x, y};
    }
}

一刷
踩到一个坑里，de了一晚上
如果比如2的board value是29，那么就没有办法通过一步到达2，只有等到譬如34的board value是2的时候才可能到达2
所以2的Step数是到达34 的Step+1
class Solution {
    public int snakesAndLadders(int[][] board) {
        int rows = board.length;
        int cols = board[0].length;
        Queue<Integer> que = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        que.offer(1);
        visited.add(1);
        int step = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            step++;
            while (size-- > 0) {
                int curr = que.poll();
                for (int k = 1; k <= 6; k++) {
                    int next = curr + k;
                    int value = getValue(next, board);
                    if (value != -1) {
                        next = value;
                    }
                    if (next == rows * cols) {
                        return step;
                    }
                    if (visited.contains(next)) {
                        continue;
                    }
                    que.offer(next);
                    visited.add(next);
                }
             
            }
        }
     
        return -1;
    }
 
    private int getValue(int S, int[][] board) {
        int rows = board.length;
        int cols = board[0].length;
        S--;
        int x = rows - 1 - S / cols;
        int y = (S / cols % 2) == 0 ? S % cols : cols - 1 - S % cols;
        return board[x][y];
    }
}