2025年909. 蛇梯棋（图的BFS）

编程基础 • 2025-02-26 14:46 • 阅读 18

使用广度优先搜索来遍历从1到n*n的可能的路径。

这道题可以看作一个有向图，每个值为x的节点指向x+1点节点，在蛇桥处，是从x指向y

注意这里的x、x+1、y都是值，可以根据值计算出对应的行列值，计算规则：
假设值为nxt，
则对应的r为(nxt-1)/n，由于nxt的值是从下往上依次递增，而board的行列值是从上往下递增，因此最终返回的行应该是n-1-(nxt-1)/n
对应的c为(nxt-1)%n，由于是s型，所以要根据r的奇偶来区分不同的c值，当r为奇数时，c取n-1-(nxt-1)%n，当r为偶数时，c取(nxt-1)%n，这里的r是(nxt-1)/n，也就是从下往上递增的。

除此之外，还要注意蛇桥位置不计入步数，所以在确定r和c后，要判断这里是否存在蛇桥，一步到位，然后再判断一步到位之后的位置和n*n之间的关系。

class Solution {
   
    public int snakesAndLadders(int[][] board) {
   
        int n = board.length;
        boolean[] vis = new boolean[n * n + 1];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {
   1, 0});
        while (!q.isEmpty()) {
   
            int[] p = q.poll();
            // 扔骰子点数为：1-6
            for (int i = 1; i <= 6; ++i) {
   
                int nxt = p[0] + i;
                if (nxt > n * n) break;
                int[] rc = idx2rc(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;
                    q.offer(new int[] {
   nxt, p[1] + 1});
                }
            }
        }
        return -1;
    }

    private int[] idx2rc(int nxt, int n) {
   
        int r = (nxt - 1) / n;
        int c = r % 2 == 0 ? (nxt - 1) % n : n - 1 - (nxt - 1) % n;
        return new int[] {
   n - 1 - r, c};
    }
}

2025年909. 蛇梯棋（图的BFS）

相关推荐