LeetCode 773. 滑动谜题

字数 2451 2025-10-26 19:15:22

LeetCode 773. 滑动谜题

题目描述

在一个 2x3 的棋盘上，有 5 块编号为 1 到 5 的方块，以及一个空位（用 0 表示）。一次移动定义为选择 0 这个空格，将其与相邻的方块（上下左右）进行交换。

给定棋盘的初始状态 board（一个 2x3 的二维数组），例如 [[1,2,3],[4,0,5]]，你的任务是计算出需要的最少移动次数，使得棋盘变为目标状态 [[1,2,3],[4,5,0]]。如果无法完成这个转换，则返回 -1。

解题过程

这个题目本质上是一个最短路径搜索问题。我们可以将每一种棋盘状态看作图中的一个节点，如果状态 A 可以通过一次移动（交换 0 和相邻数字）变成状态 B，那么图中就存在一条从节点 A 到节点 B 的边。我们的目标就是找到从初始状态节点到目标状态节点的最短路径（边数）。

由于状态空间不大（6! 种排列，但 0 的位置固定了排列方式，实际是 6! / 6 = 120 种可能状态？这里需要精确计算：实际上是 6 个位置放 6 个不同的数，但 0 等价于空格，所以是 6! = 720 种不同的棋盘状态），我们可以使用 广度优先搜索（BFS） 来寻找最短路径。BFS 的优势在于，它第一次探索到目标状态时，所用的步数就是最短路径。

循序渐进讲解

状态表示与目标状态
为了便于处理（比如放入哈希集合进行判重），我们需要将一个 2x3 的二维数组“扁平化”成一个字符串。例如，初始状态 [[1,2,3],[4,0,5]] 可以表示为字符串 "123405"。目标状态 [[1,2,3],[4,5,0]] 则对应字符串 "123450"。
- 目标：我们的目标就是将表示初始状态的字符串，通过最少的交换次数，变成 "123450"。
BFS 的核心要素
BFS 需要两个主要数据结构：
- 队列（Queue）：用于存储待探索的状态，以及到达该状态所需的步数。我们通常将 (当前状态字符串, 已走步数) 作为一个元素存入队列。
- 已访问集合（Visited Set）：用于记录已经探索过的状态，避免重复访问和陷入循环。
邻居状态的生成（关键步骤）
这是本题最核心的部分。对于一个给定的状态字符串（例如 "123405"），我们如何找出所有通过一次移动能得到的新状态？
- 步骤 A：找到空格（‘0’）的位置。 在字符串 "123405" 中，字符 ‘0’ 在索引 4 的位置（索引从 0 开始）。我们需要知道这个索引在 2x3 棋盘上对应的坐标 (row, col)。转换公式是：row = index / 3, col = index % 3。所以索引 4 对应坐标 (1, 1)。
- 步骤 B：确定空格可以移动的方向。 从坐标 (1, 1) 出发，它可以与上下左右四个方向的格子交换。但是需要注意边界条件：向上不能超出第 0 行，向下不能超出第 1 行，向左不能小于第 0 列，向右不能超出第 2 列。
- 步骤 C：对每个可行的方向，交换空格和目标数字，生成新状态。
  - 以向右移动为例：空格 (1,1) 的右边是 (1,2)。我们需要计算这个邻居坐标在字符串中的索引：new_index = new_row * 3 + new_col = 1*3 + 2 = 5。
  - 现在，原字符串中索引 4 是 ‘0’，索引 5 是 ‘5’。我们交换这两个位置的字符。
  - 原字符串: 1 2 3 4 0 5 (索引: 0,1,2,3,4,5)
  - 交换后字符串: 1 2 3 4 5 0 (索引 4 和 5 的字符互换)
  - 这样我们就得到了一个新的状态 "123450"。
为了方便，我们可以预先定义一个“邻居映射表”。这个表告诉我们，在扁平化的一维字符串索引中，每个位置索引的邻居索引有哪些。
- 索引 0 的邻居是 [1, 3]
- 索引 1 的邻居是 [0, 2, 4]
- 索引 2 的邻居是 [1, 5]
- 索引 3 的邻居是 [0, 4]
- 索引 4 的邻居是 [1, 3, 5]
- 索引 5 的邻居是 [2, 4]
  有了这个映射表，对于任何状态，我们只需要找到 ‘0’ 的索引，然后根据映射表得到它能交换的所有邻居索引，依次进行交换即可生成新状态。
BFS 算法步骤
- 初始化：
  - 将初始状态字符串 start 和步数 0 作为元组 (start, 0) 放入队列。
  - 将 start 加入已访问集合。
- 循环直到队列为空：
  - 从队列中取出一个状态 current 和对应的步数 steps。
  - 如果 current 等于目标字符串 "123450"，则返回 steps。
  - 否则，找到 current 字符串中字符 ‘0’ 的索引 idx。
  - 根据我们预先定义好的“邻居映射表”，找到 idx 的所有邻居索引。
  - 遍历每一个邻居索引 neighbor_idx：
    - 将字符串 current 转换为一个字符列表（因为字符串在 Python 中是不可变的，无法直接交换字符）。
    - 在这个字符列表中，交换位置 idx 和位置 neighbor_idx 的字符。
    - 将交换后的字符列表重新连接成一个新的字符串 new_state。
    - 检查 new_state 是否不在已访问集合中。
    - 如果不在，说明这是一个新状态：
      - 将 (new_state, steps + 1) 加入队列。
      - 将 new_state 加入已访问集合，表示已经探索过。
- 如果队列为空仍未找到目标状态，说明从初始状态无法到达目标状态，返回 -1。

总结
这道题巧妙地将一个二维滑动谜题抽象为图论中的最短路径问题。通过 BFS 一层层扩展状态，确保第一次遇到目标状态时所用的步数就是最小的。其中，将棋盘状态字符串化以及预先计算邻居索引映射表，是简化代码和逻辑的关键技巧。

LeetCode 773. 滑动谜题题目描述在一个 2x3 的棋盘上，有 5 块编号为 1 到 5 的方块，以及一个空位（用 0 表示）。一次移动定义为选择 0 这个空格，将其与相邻的方块（上下左右）进行交换。给定棋盘的初始状态 board （一个 2x3 的二维数组），例如 [[1,2,3],[4,0,5]] ，你的任务是计算出需要的最少移动次数，使得棋盘变为目标状态 [[1,2,3],[4,5,0]] 。如果无法完成这个转换，则返回 -1。解题过程这个题目本质上是一个最短路径搜索问题。我们可以将每一种棋盘状态看作图中的一个节点，如果状态 A 可以通过一次移动（交换 0 和相邻数字）变成状态 B，那么图中就存在一条从节点 A 到节点 B 的边。我们的目标就是找到从初始状态节点到目标状态节点的最短路径（边数）。由于状态空间不大（6! 种排列，但 0 的位置固定了排列方式，实际是 6! / 6 = 120 种可能状态？这里需要精确计算：实际上是 6 个位置放 6 个不同的数，但 0 等价于空格，所以是 6! = 720 种不同的棋盘状态），我们可以使用广度优先搜索（BFS）来寻找最短路径。BFS 的优势在于，它第一次探索到目标状态时，所用的步数就是最短路径。循序渐进讲解状态表示与目标状态为了便于处理（比如放入哈希集合进行判重），我们需要将一个 2x3 的二维数组“扁平化”成一个字符串。例如，初始状态 [[1,2,3],[4,0,5]] 可以表示为字符串 "123405" 。目标状态 [[1,2,3],[4,5,0]] 则对应字符串 "123450" 。目标：我们的目标就是将表示初始状态的字符串，通过最少的交换次数，变成 "123450" 。 BFS 的核心要素 BFS 需要两个主要数据结构：队列（Queue）：用于存储待探索的状态，以及到达该状态所需的步数。我们通常将 (当前状态字符串, 已走步数) 作为一个元素存入队列。已访问集合（Visited Set）：用于记录已经探索过的状态，避免重复访问和陷入循环。邻居状态的生成（关键步骤）这是本题最核心的部分。对于一个给定的状态字符串（例如 "123405" ），我们如何找出所有通过一次移动能得到的新状态？步骤 A：找到空格（‘0’）的位置。在字符串 "123405" 中，字符 ‘0’ 在索引 4 的位置（索引从 0 开始）。我们需要知道这个索引在 2x3 棋盘上对应的坐标 (row, col) 。转换公式是： row = index / 3 , col = index % 3 。所以索引 4 对应坐标 (1, 1)。步骤 B：确定空格可以移动的方向。从坐标 (1, 1) 出发，它可以与上下左右四个方向的格子交换。但是需要注意边界条件：向上不能超出第 0 行，向下不能超出第 1 行，向左不能小于第 0 列，向右不能超出第 2 列。步骤 C：对每个可行的方向，交换空格和目标数字，生成新状态。以向右移动为例：空格 (1,1) 的右边是 (1,2)。我们需要计算这个邻居坐标在字符串中的索引： new_index = new_row * 3 + new_col = 1*3 + 2 = 5 。现在，原字符串中索引 4 是 ‘0’，索引 5 是 ‘5’。我们交换这两个位置的字符。原字符串: 1 2 3 4 0 5 (索引: 0,1,2,3,4,5) 交换后字符串: 1 2 3 4 5 0 (索引 4 和 5 的字符互换) 这样我们就得到了一个新的状态 "123450" 。为了方便，我们可以预先定义一个“邻居映射表”。这个表告诉我们，在扁平化的一维字符串索引中，每个位置索引的邻居索引有哪些。索引 0 的邻居是 [ 1, 3 ] 索引 1 的邻居是 [ 0, 2, 4 ] 索引 2 的邻居是 [ 1, 5 ] 索引 3 的邻居是 [ 0, 4 ] 索引 4 的邻居是 [ 1, 3, 5 ] 索引 5 的邻居是 [ 2, 4 ] 有了这个映射表，对于任何状态，我们只需要找到 ‘0’ 的索引，然后根据映射表得到它能交换的所有邻居索引，依次进行交换即可生成新状态。 BFS 算法步骤初始化：将初始状态字符串 start 和步数 0 作为元组 (start, 0) 放入队列。将 start 加入已访问集合。循环直到队列为空：从队列中取出一个状态 current 和对应的步数 steps 。如果 current 等于目标字符串 "123450" ，则返回 steps 。否则，找到 current 字符串中字符 ‘0’ 的索引 idx 。根据我们预先定义好的“邻居映射表”，找到 idx 的所有邻居索引。遍历每一个邻居索引 neighbor_idx ：将字符串 current 转换为一个字符列表（因为字符串在 Python 中是不可变的，无法直接交换字符）。在这个字符列表中，交换位置 idx 和位置 neighbor_idx 的字符。将交换后的字符列表重新连接成一个新的字符串 new_state 。检查 new_state 是否不在已访问集合中。如果不在，说明这是一个新状态：将 (new_state, steps + 1) 加入队列。将 new_state 加入已访问集合，表示已经探索过。如果队列为空仍未找到目标状态，说明从初始状态无法到达目标状态，返回 -1。总结这道题巧妙地将一个二维滑动谜题抽象为图论中的最短路径问题。通过 BFS 一层层扩展状态，确保第一次遇到目标状态时所用的步数就是最小的。其中，将棋盘状态字符串化以及预先计算邻居索引映射表，是简化代码和逻辑的关键技巧。