LeetCode 773. 滑动谜题
字数 2459 2025-11-05 08:30:58

LeetCode 773. 滑动谜题

题目描述

在一个 2x3 的棋盘上，有 5 块编号为 1 到 5 的方块，以及一个空位（用 0 表示）。拼图的状态可以用一个长度为 6 的数组 board 表示，其中 board[i] 表示位置 i 上的方块编号（0 代表空位）。位置索引如下所示：
0 1 2
3 4 5

谜题的目标是通过移动方块，使得棋盘变为最终状态 [[1,2,3],[4,5,0]]。每一次移动的操作是：将空位相邻（上下左右）的一个方块滑动到空位中。

给定一个初始棋盘状态 board（也是一个长度为 6 的数组），你需要计算出完成拼图的最少移动次数。如果无法完成拼图，则返回 -1。

解题过程

这个问题可以被视为在一个状态图上寻找从初始状态到目标状态的最短路径。每个状态是棋盘的一种排列，每次移动（即空位与相邻方块交换）会转换到新的状态。

  1. 问题抽象与状态表示

    • 核心是将一个具体的棋盘拼图问题，转化为一个图论中的最短路径问题。
    • 节点（Node）：每一个可能的棋盘布局就是一个节点。对于 2x3 的棋盘，总共有 6! 种排列，但其中只有一半是可以通过移动空位达到的（类似于数字华容道的奇偶性），不过我们无需预先计算，在搜索中处理即可。
    • 边（Edge）：如果通过一次合法的移动（滑动一个相邻方块到空位），可以从一个棋盘状态 A 转换到另一个棋盘状态 B，那么我们就认为节点 A 和节点 B 之间存在一条无向边，且边的权重为 1（因为一次移动就是一步）。
    • 目标：找到从代表初始状态的节点到代表目标状态 [1,2,3,4,5,0] 的节点的最短路径长度（步数）。

  2. 选择搜索算法：广度优先搜索（BFS）

    • 由于每次移动的代价都是 1（等权图），并且我们需要的是最少移动次数，广度优先搜索（BFS） 是最佳选择。BFS 的特性是它会首先探索所有距离起点为 1 步的节点，然后是距离为 2 步的节点，以此类推。因此，当 BFS 第一次遇到目标状态时，当前的步数就一定是最短路径长度。

  3. 关键实现细节

    • 状态的表示与存储：我们需要一种方式来表示一个棋盘状态，并能够判断某个状态是否已经被访问过，以避免重复搜索和死循环。最直接的方式是使用一个长度为 6 的字符串或元组来表示棋盘。例如，状态 [1,2,3,4,0,5] 可以表示为字符串 "123405"。我们使用一个集合（例如 visited）来存储所有已经访问过的状态字符串。
    • 空位（0）的邻居映射：为了生成新的状态，我们需要知道当前空位在哪个位置，以及它可以和哪些位置交换。我们可以预先定义一个“邻居映射”字典。字典的键是空位所在的位置索引（0到5），值是一个列表，包含所有可以与空位交换的相邻位置的索引。
      • 位置 0 的邻居是 [1, 3]
      • 位置 1 的邻居是 [0, 2, 4]
      • 位置 2 的邻居是 [1, 5]
      • 位置 3 的邻居是 [0, 4]
      • 位置 4 的邻居是 [1, 3, 5]
      • 位置 5 的邻居是 [2, 4]
    • 状态转换（移动）：从一个给定的状态（字符串）出发，我们首先找到空位 ‘0’ 的索引 zero_idx。然后，根据上面定义的邻居映射，找到所有可以与空位交换的位置索引 neighbor_idx。对于每一个邻居索引，我们创建一个当前状态字符串的列表副本，交换 zero_idx 和 neighbor_idx 两个位置的字符，从而生成一个新的状态字符串。这个新字符串就是通过一次移动可以到达的新状态。

  4. 算法步骤（BFS框架）

    • 步骤 1：初始化

      • 将初始状态数组转换为一个字符串 start（例如，将 [1,2,3,4,0,5] 转为 "123405"）。
      • 定义目标状态字符串 target = "123450"。
      • 创建一个队列 queue，并将元组 (start, 0) 入队。这个元组表示（当前状态，到达该状态所需的步数）。初始步数为 0。
      • 创建一个已访问集合 visited，并将 start 加入集合。

    • 步骤 2：BFS 循环

      • 当队列不为空时循环：
        • 从队列中出队一个元素，得到当前状态 current_state 和当前步数 steps。
        • 检查是否到达目标：如果 current_state 等于 target，则搜索成功，返回 steps。
        • 寻找空位和邻居：在 current_state 中找到字符 ‘0’ 的的位置 zero_idx。
        • 生成新状态：遍历 zero_idx 的所有邻居位置 neighbor_idx（通过预定义的邻居映射字典）：
          • 将 current_state 转换为一个字符列表（如 list(current_state)），因为字符串是不可变的，无法直接交换。
          • 交换这个列表中 zero_idx 和 neighbor_idx 位置的两个字符。
          • 将交换后的字符列表重新组合成一个新的字符串 new_state。
        • 检查并处理新状态：
          • 如果 new_state 不在 visited 集合中，说明我们找到了一个未被访问的新状态。
          • 将 new_state 加入 visited 集合，以避免重复访问。
          • 将元组 (new_state, steps + 1) 加入队列。这表示到达 new_state 需要比当前状态多一步。

    • 步骤 3：处理无解情况

      • 如果 BFS 循环结束（队列为空）我们还没有遇到目标状态，说明从初始状态无法到达目标状态，返回 -1。

总结

通过将棋盘状态抽象为图的节点，将移动操作抽象为边，我们成功地将一个滑动谜题问题转化为了一个标准的最短路径问题。利用 BFS 逐层遍历的特性，我们能够高效地找到最少移动次数（如果存在解的话）。这个解法的核心在于状态表示、邻居映射以及 BFS 的标准框架应用。

LeetCode 773. 滑动谜题 题目描述 在一个 2x3 的棋盘上，有 5 块编号为 1 到 5 的方块，以及一个空位（用 0 表示）。拼图的状态可以用一个长度为 6 的数组 board 表示，其中 board[i] 表示位置 i 上的方块编号（0 代表空位）。位置索引如下所示： 0 1 2 3 4 5 谜题的目标是通过移动方块，使得棋盘变为最终状态 [[1,2,3],[4,5,0]] 。每一次移动的操作是：将空位相邻（上下左右）的一个方块滑动到空位中。 给定一个初始棋盘状态 board （也是一个长度为 6 的数组），你需要计算出完成拼图的最少移动次数。如果无法完成拼图，则返回 -1。 解题过程 这个问题可以被视为在一个状态图上寻找从初始状态到目标状态的最短路径。每个状态是棋盘的一种排列，每次移动（即空位与相邻方块交换）会转换到新的状态。 问题抽象与状态表示 核心是将一个具体的棋盘拼图问题，转化为一个图论中的 最短路径问题 。 节点（Node） ：每一个可能的棋盘布局就是一个节点。对于 2x3 的棋盘，总共有 6 ! 种排列，但其中只有一半是可以通过移动空位达到的（类似于数字华容道的奇偶性），不过我们无需预先计算，在搜索中处理即可。 边（Edge） ：如果通过一次合法的移动（滑动一个相邻方块到空位），可以从一个棋盘状态 A 转换到另一个棋盘状态 B，那么我们就认为节点 A 和节点 B 之间存在一条无向边，且边的权重为 1（因为一次移动就是一步）。 目标 ：找到从代表初始状态的节点到代表目标状态 [1,2,3,4,5,0] 的节点的最短路径长度（步数）。 选择搜索算法：广度优先搜索（BFS） 由于每次移动的代价都是 1（等权图），并且我们需要的是 最少移动次数 ， 广度优先搜索（BFS） 是最佳选择。BFS 的特性是它会首先探索所有距离起点为 1 步的节点，然后是距离为 2 步的节点，以此类推。因此，当 BFS 第一次遇到目标状态时，当前的步数就一定是最短路径长度。 关键实现细节 状态的表示与存储 ：我们需要一种方式来表示一个棋盘状态，并能够判断某个状态是否已经被访问过，以避免重复搜索和死循环。最直接的方式是使用一个长度为 6 的字符串或元组来表示棋盘。例如，状态 [1,2,3,4,0,5] 可以表示为字符串 "123405" 。我们使用一个集合（例如 visited ）来存储所有已经访问过的状态字符串。 空位（0）的邻居映射 ：为了生成新的状态，我们需要知道当前空位在哪个位置，以及它可以和哪些位置交换。我们可以预先定义一个“邻居映射”字典。字典的键是空位所在的位置索引（0到5），值是一个列表，包含所有可以与空位交换的相邻位置的索引。 位置 0 的邻居是 [ 1, 3 ] 位置 1 的邻居是 [ 0, 2, 4 ] 位置 2 的邻居是 [ 1, 5 ] 位置 3 的邻居是 [ 0, 4 ] 位置 4 的邻居是 [ 1, 3, 5 ] 位置 5 的邻居是 [ 2, 4 ] 状态转换（移动） ：从一个给定的状态（字符串）出发，我们首先找到空位 ‘0’ 的索引 zero_idx 。然后，根据上面定义的邻居映射，找到所有可以与空位交换的位置索引 neighbor_idx 。对于每一个邻居索引，我们创建一个当前状态字符串的列表副本，交换 zero_idx 和 neighbor_idx 两个位置的字符，从而生成一个新的状态字符串。这个新字符串就是通过一次移动可以到达的新状态。 算法步骤（BFS框架） 步骤 1：初始化 将初始状态数组转换为一个字符串 start （例如，将 [1,2,3,4,0,5] 转为 "123405" ）。 定义目标状态字符串 target = "123450" 。 创建一个队列 queue ，并将元组 (start, 0) 入队。这个元组表示（当前状态，到达该状态所需的步数）。初始步数为 0。 创建一个已访问集合 visited ，并将 start 加入集合。 步骤 2：BFS 循环 当队列不为空时循环： 从队列中出队一个元素，得到当前状态 current_state 和当前步数 steps 。 检查是否到达目标 ：如果 current_state 等于 target ，则搜索成功，返回 steps 。 寻找空位和邻居 ：在 current_state 中找到字符 ‘0’ 的的位置 zero_idx 。 生成新状态 ：遍历 zero_idx 的所有邻居位置 neighbor_idx （通过预定义的邻居映射字典）： 将 current_state 转换为一个字符列表（如 list(current_state) ），因为字符串是不可变的，无法直接交换。 交换这个列表中 zero_idx 和 neighbor_idx 位置的两个字符。 将交换后的字符列表重新组合成一个新的字符串 new_state 。 检查并处理新状态 ： 如果 new_state 不在 visited 集合中，说明我们找到了一个未被访问的新状态。 将 new_state 加入 visited 集合，以避免重复访问。 将元组 (new_state, steps + 1) 加入队列。这表示到达 new_state 需要比当前状态多一步。 步骤 3：处理无解情况 如果 BFS 循环结束（队列为空）我们还没有遇到目标状态，说明从初始状态无法到达目标状态，返回 -1。 总结 通过将棋盘状态抽象为图的节点，将移动操作抽象为边，我们成功地将一个滑动谜题问题转化为了一个标准的最短路径问题。利用 BFS 逐层遍历的特性，我们能够高效地找到最少移动次数（如果存在解的话）。这个解法的核心在于状态表示、邻居映射以及 BFS 的标准框架应用。