909. Snakes and Ladders

Posted on | Edited on | Views:

LeetCode

link
Breadth-First Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution{
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        boolean[] visited = new boolean[n * n + 1];
        for (int move = 0; !queue.isEmpty(); move++) {
            for (int size = queue.size(); size > 0; size--) {
                int num = queue.poll();
                if (num == n * n) return move;
                if (!visited[num]) {
                    visited[num] = true;   
                    for (int i = 1; i <= 6 && num + i <= n * n; i++) {
                        int next = num + i;
                        int value = getBoardValue(board, next);
                        if (value > 0) next = value;
                        if (!visited[next]) queue.offer(next);
                    }
                }
            }
        }
        return -1;
    }

    private int getBoardValue(int[][] board, int num) {
        int n = board.length;
        int oldRow = (num - 1) / n;
        int row = n-1 -oldRow;
        int oldCol = (num-1) % n;
        int col = oldRow % 2 == 0 ? oldCol : n - 1 - oldCol;
        
        return board[row][col];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
class Solution{
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        boolean[] visited = new boolean[n * n + 1];
        int move = 0;
        while(!queue.isEmpty()){
            int qsize=queue.size();
            for (int size =0;size < qsize;size++) {      
                int num = queue.poll();
                if (num == n * n) return move;
                if (!visited[num]){
                    visited[num] = true;
                    for (int i = 1; i <= 6 && num + i <= n * n; i++) {
                        int next = num + i;
                        int value = getBoardValue(board, next);
                        if (value > 0) next = value;
                        if (!visited[next]) queue.offer(next);
                    }
                }
            }
            move++;
        }
        return -1;
    }

    private int getBoardValue(int[][] board, int num) {
        int n = board.length;
        int oldRow = (num - 1) / n;
        int row = n-1 -oldRow;
        int oldCol = (num-1) % n;
        int col = oldRow % 2 == 0 ? oldCol : n - 1 - oldCol;
        
        return board[row][col];
    }
}*/
0%