LC.P909[蛇梯棋]

方法一：BFS

由于题目中n的范围最大为20，因此可将二维矩阵扁平化为一维矩阵，利用单向BFS求解

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
39
class Solution {
    int n;
    int[] nums;

    public int snakesAndLadders(int[][] board) {
        if (board[0][0] != -1) return -1;
        n = board.length;
        nums = new int[n * n + 1];
        boolean flag = true;
        for (int i = n - 1, index = 1; i >= 0; --i) {
            for (int j = flag ? 0 : n - 1; flag ? j < n : j >= 0; j += flag ? 1 : -1) {
                nums[index++] = board[i][j];
            }
            flag = !flag;
        }
        return bfs();
    }

    private int bfs() {
        Deque<Integer> queue = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        queue.offer(1);
        map.put(1, 0);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int step = map.get(cur);
            if (cur == n * n) return step;
            for (int i = 1; i <= 6; ++i) {
                int ni = cur + i;
                if (ni <= 0 || ni > n * n) continue;
                if (nums[ni] != -1) ni = nums[ni];
                if (map.containsKey(ni)) continue;
                map.put(ni, step + 1);
                queue.offer(ni);
            }
        }
        return -1;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$