LeetCode 909. 蛇梯棋

Categories:

题目描述
思路分析
1. 解法一：BFS 最短路径（推荐）
相似题目

题目描述

✅ 909. 蛇梯棋

思路分析

解法一：BFS 最短路径（推荐）

核心思路：

将棋盘编号为 1 到 n^2，按“之”字形映射到坐标。

预处理每个编号的跳转目标，若有蛇/梯则指向终点。

BFS 从 1 出发，扩展 1~6 步可达位置，首次到达终点即最短步数。

复杂度分析：

时间复杂度：O(n^2)，每个格子最多入队一次。

空间复杂度：O(n^2)，队列与访问数组。

import java.util.*;

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int target = n * n;
        int[] move = new int[target + 1];
        for (int i = 1; i <= target; i++) {
            int[] pos = idToPos(i, n);
            int r = pos[0];
            int c = pos[1];
            if (board[r][c] == -1) {
                move[i] = i;
            } else {
                move[i] = board[r][c];
            }
        }

        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[target + 1];
        queue.offer(1);
        visited[1] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (cur == target) {
                    return steps;
                }
                for (int d = 1; d <= 6 && cur + d <= target; d++) {
                    int next = move[cur + d];
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
            steps++;
        }

        return -1;
    }

    private int[] idToPos(int id, int n) {
        int r = n - 1 - (id - 1) / n;
        int c = (id - 1) % n;
        if (((n - 1 - r) & 1) == 1) {
            c = n - 1 - c;
        }
        return new int[]{r, c};
    }
}

func snakesAndLadders(board [][]int) int {
    n := len(board)
    target := n * n
    move := make([]int, target+1)
    for i := 1; i <= target; i++ {
        r, c := idToPos(i, n)
        if board[r][c] == -1 {
            move[i] = i
        } else {
            move[i] = board[r][c]
        }
    }

    queue := []int{1}
    visited := make([]bool, target+1)
    visited[1] = true
    steps := 0

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]
            if cur == target {
                return steps
            }
            for d := 1; d <= 6 && cur+d <= target; d++ {
                next := move[cur+d]
                if !visited[next] {
                    visited[next] = true
                    queue = append(queue, next)
                }
            }
        }
        steps++
    }

    return -1
}

func idToPos(id int, n int) (int, int) {
    r := n - 1 - (id-1)/n
    c := (id - 1) % n
    if ((n-1-r)&1) == 1 {
        c = n - 1 - c
    }
    return r, c
}

相似题目

题目	难度	考察点
752. 打开转盘锁	中等	BFS
127. 单词接龙	困难	BFS
773. 滑动谜题	困难	BFS
1091. 二进制矩阵中的最短路径	中等	BFS
994. 腐烂的橘子	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/89174011