跳至主要內容

909. 蛇梯棋

909. 蛇梯棋open in new window

🟠   🔖  广度优先搜索 数组 矩阵  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon styleopen in new window starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

  • Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].
    • This choice simulates the result of a standard 6-sided die roll : i.e., there are always at most 6 destinations, regardless of the size of the board.
  • If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
  • The game ends when you reach the square n2.

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 are not the starting points of any snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

  • For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of moves required to reach the squaren2 . If it is not possible to reach the square, return-1.

Example 1:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]

Output: 4

Explanation:

In the beginning, you start at square 1 (at row 5, column 0).

You decide to move to square 2 and must take the ladder to square 15.

You then decide to move to square 17 and must take the snake to square 13.

You then decide to move to square 14 and must take the ladder to square 35.

You then decide to move to square 36, ending the game.

This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]]

Output: 1

Constraints:

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] is either -1 or in the range [1, n2].
  • The squares labeled 1 and n2 are not the starting points of any snake or ladder.

题目大意

给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式open in new window ，从左下角开始 （即，从 board[n - 1][0] 开始）的每一行改变方向。

你一开始位于棋盘上的方格 1。每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

  • 选定目标方格 next ，目标方格的编号在范围 [curr + 1, min(curr + 6, n2)] 。
    • 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。
  • 传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。
  • 当玩家到达编号 n2 的方格时，游戏结束。

如果 board[r][c] != -1 ，位于 r 行 c 列的棋盘格中可能存在 “蛇” 或 “梯子”。那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格不是任何蛇或梯子的起点。

注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。

  • 举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但 不能 顺着方格 3 上的梯子前往方格 4 。（简单来说，类似飞行棋，玩家掷出骰子点数后移动对应格数，遇到单向的路径（即梯子或蛇）可以直接跳到路径的终点，但如果多个路径首尾相连，也不能连续跳多个路径）

返回达到编号为 n2 的方格所需的最少移动次数，如果不可能，则返回 -1。

示例 1：

输入： board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]

输出： 4

解释：

首先，从方格 1 [第 5 行，第 0 列] 开始。

先决定移动到方格 2 ，并必须爬过梯子移动到到方格 15 。

然后决定移动到方格 17 [第 3 行，第 4 列]，必须爬过蛇到方格 13 。

接着决定移动到方格 14 ，且必须通过梯子移动到方格 35 。

最后决定移动到方格 36 , 游戏结束。

可以证明需要至少 4 次移动才能到达最后一个方格，所以答案是 4 。

示例 2：

输入： board = [[-1,-1],[-1,3]]

输出： 1

提示：

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] 的值是 -1 或在范围 [1, n2] 内
  • 编号为 1 和 n2 的方格上没有蛇或梯子

解题思路

这是一道经典的广度优先搜索（BFS）题，可以将棋盘上的格子看作是图中的节点，骰子每次掷出的 1 到 6 个点表示节点之间的边，蛇和梯子则是特殊的移动规则。

  1. 棋盘展平：

    • 我们需要先把二维数组 board 变为一维的，方便进行线性搜索（因为棋盘上的数字是连续的）。
    • 从左往右、从右往左依次交替走棋盘的每一行，确保与棋盘上的编号一致。

  2. 广度优先搜索：

    • 使用队列存储每次可能的下一步移动。
    • 从起始位置 1 开始，每次投骰子可以从 1 到 6 步，每一步到达一个新的位置。如果该位置上有梯子或蛇，就直接传送到指定的目标位置。
    • 为了避免重复访问位置，需要记录访问过的位置（visited）。

  3. 终止条件：

    • 当到达最后一格 n * n 时，返回移动的次数。
    • 如果队列遍历结束还没到达终点，返回 -1 表示无法到达。

复杂度分析

  • 时间复杂度：O(n^2)，因为棋盘的大小是 n * n，最坏情况下每个格子都需要被访问一次。
  • 空间复杂度：O(n^2)，使用队列和访问记录数组 visited 来存储棋盘上的状态信息。

代码

/**
 * @param {number[][]} board
 * @return {number}
 */
var snakesAndLadders = function (board) {
	const n = board.length;
	const visited = new Array(n * n + 1).fill(false);

	// 将二维的board转换为一维的数组
	const getBoardValue = (num) => {
		const r = Math.floor((num - 1) / n);
		const x = n - 1 - r;
		const y = r % 2 === 0 ? (num - 1) % n : n - 1 - ((num - 1) % n);
		return board[x][y];
	};

	const queue = [[1, 0]]; // [position, moves]
	visited[1] = true;

	while (queue.length > 0) {
		const [pos, moves] = queue.shift();

		// 如果到达终点
		if (pos === n * n) return moves;

		// 掷骰子，尝试走 1-6 步
		for (let i = 1; i <= 6; i++) {
			let next = pos + i;
			if (next > n * n) break;

			const boardValue = getBoardValue(next);
			if (boardValue !== -1) {
				next = boardValue; // 如果有梯子或蛇，跳到目标位置
			}

			if (!visited[next]) {
				visited[next] = true;
				queue.push([next, moves + 1]);
			}
		}
	}

	return -1; // 如果不能到达终点
};

相关题目

题号标题题解标签难度
2467树上最大得分和路径open in new window树 深度优先搜索 广度优先搜索 2+
Copyright © 2024 2xiao