909 蛇梯棋

题目描述#

给一个 n x n 的棋盘，格子按"转行交替"方式从 1 到 n² 编号，从左下角开始，奇数行从左往右、偶数行从右往左（从底部数）。每次掷骰子可以前进 1 到 6 格，落点若有蛇或梯子则强制跳转（只跳一次）。求从格子 1 到格子 n² 所需的最少掷骰次数，不可达则返回 -1。

思路#

本题是无权图上的最短路径，用 BFS 逐层扩展即可。每一层代表一次掷骰，当第一次到达终点时返回当前层数。

核心难点在于编号到二维坐标的转换。将编号减一转为 0-indexed，先算出从底部数的行号 row = s / n，再算列号 col = s % n；实际行号为 r = n - 1 - row。奇数行（从底部数）是从右往左排列，需要把列号翻转：col = n - 1 - col。

BFS 每次从队列取出当前格子，枚举骰子 1 到 6，算出落点 next，若有跳转则更新为目标格；若未访问则入队。注意终点判断要在跳转之后进行，因为蛇或梯子可能直接通向终点。

知识边界#

最少步数 → BFS，不要用 DFS
编号转二维坐标：奇偶行方向相反，需要对列号翻转，这是本题最容易出错的地方
蛇/梯子只跳一次：跳转后不再触发下一个跳转，直接入队即可
visited 数组标记的是跳转后的最终落点，而不是骰子的直接落点，避免同一格被多路径重复入队

代码#

func snakesAndLadders(board [][]int) int {
	n := len(board)

	// 编号转坐标
	numToPos := func(s int) (int, int) {
		s-- // 转 0-indexed
		row := s / n
		col := s % n
		r := n - 1 - row
		// 奇数行（从底部数）从右往左
		if row%2 == 1 {
			col = n - 1 - col
		}
		return r, col
	}

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

	for len(queue) > 0 {
		size := len(queue)
		steps++
		for i := 0; i < size; i++ {
			curr := queue[i]
			for dice := 1; dice <= 6; dice++ {
				next := curr + dice
				if next > n*n {
					break
				}
				r, c := numToPos(next)
				if board[r][c] != -1 {
					next = board[r][c] // 有蛇或梯子，跳转
				}
				if next == n*n {
					return steps
				}
				if !visited[next] {
					visited[next] = true
					queue = append(queue, next)
				}
			}
		}
		queue = queue[size:]
	}
	return -1
}