LeetCode 773. 滑动谜题

字数 1918 2025-11-05 23:45:49

LeetCode 773. 滑动谜题

题目描述：
在一个 2x3 的棋盘上，有 5 块编号为 1 到 5 的方块，以及一个空缺（用 0 表示）。谜题的目标是利用这个空缺，通过移动方块，使得棋盘变为目标状态 [[1,2,3],[4,5,0]]。每次移动可以选择与空缺相邻（上下左右）的一个方块，将其滑入空缺位置。给定一个初始棋盘状态 board，你需要计算出完成谜题的最少移动次数。如果无法完成，则返回 -1。

解题过程：

问题分析：
- 这是一个典型的状态搜索问题。每个棋盘布局可以看作图中的一个节点。
- 一次合法的移动（滑动一个与0相邻的方块）相当于在图中从一个节点移动到相邻的节点。
- 我们需要找到从初始状态节点到目标状态节点的最短路径（最少移动次数）。这提示我们使用广度优先搜索（BFS），因为BFS天然地按层（按距离）遍历节点，首次遇到目标状态时，当前的步数就是最短路径。
状态表示：
- 直接使用 2x3 的二维数组进行比较和存储效率不高。我们可以将棋盘状态“扁平化”成一个字符串。例如，棋盘 [[1,2,3],[4,0,5]] 可以表示为字符串 "123405"。
- 使用字符串可以方便地判断状态是否被访问过（使用哈希集合 visited），并且方便表示目标状态（"123450"）。
寻找邻居状态（下一步可能的状态）：
- 在BFS的每一步，我们需要从当前状态衍生出所有通过一次移动能得到的新状态。
- 关键点是找到数字 0 在当前字符串中的位置 idx。
- 根据 idx 的位置，可以确定 0 可以和哪些位置的数字进行交换。我们需要一个映射关系，表示在 2x3 的棋盘上，每个索引位置（0到5）的相邻位置索引。
  - 索引布局：0 1 2 对应第一行，3 4 5 对应第二行。
  - 例如，位置0（第一行第一列）的邻居是位置1（右）和位置3（下）。
- 我们可以预先定义一个邻接表 neighbors：
  - neighbors[0] = [1, 3] (索引0的邻居是1和3)
  - neighbors[1] = [0, 2, 4] (索引1的邻居是0, 2, 4)
  - neighbors[2] = [1, 5] (索引2的邻居是1和5)
  - neighbors[3] = [0, 4] (索引3的邻居是0和4)
  - neighbors[4] = [1, 3, 5] (索引4的邻居是1, 3, 5)
  - neighbors[5] = [2, 4] (索引5的邻居是2和4)
- 对于当前状态字符串 s，找到 '0' 的索引 idx。遍历 neighbors[idx] 中的每一个邻居索引 neb。通过交换字符串 s 中 idx 和 neb 位置的字符，就可以得到一个新的状态字符串。
BFS算法步骤：
- 初始化：
  - 将初始状态（扁平化后的字符串）加入BFS队列。
  - 创建一个已访问集合 visited，将初始状态加入，防止重复访问。
  - 初始化步数 step = 0。
- BFS循环：
  - 当队列不为空时，进行循环。我们记录当前队列的大小 size（代表当前“层”的所有节点）。
  - 遍历当前层的所有 size 个节点：
    - 从队列中取出一个状态 current。
    - 如果 current 等于目标状态 "123450"，立即返回当前步数 step。
    - 否则，找到 current 中 '0' 的位置 idx。
    - 遍历 idx 的所有邻居索引 neb（从预定义的 neighbors 表中获取）：
      - 将字符串 current 转换为字符列表 chars，以便交换操作。
      - 交换 chars[idx] 和 chars[neb] 的值。
      - 将交换后的字符列表转换回新的字符串 new_state。
      - 如果 new_state 不在 visited 集合中：
        
        将其加入 visited 集合。
        
        将其加入BFS队列，等待下一层遍历。
  - 当前层的所有节点处理完毕后，步数 step 加 1，表示进入下一层（即移动次数增加一次）。
- 终止：如果BFS循环结束（队列为空）仍未找到目标状态，说明无解，返回 -1。
复杂度分析：
- 由于棋盘是 2x3，总的不同状态数是 6! (720) 种。这是一个很小的常数。
- 因此，BFS的时间和空间复杂度都可以看作是 O(1)。

这个算法通过BFS系统地探索所有可能的状态，利用预定义的邻居关系高效生成新状态，并使用哈希集合避免重复访问，从而在最短的移动次数内找到解或判断无解。

LeetCode 773. 滑动谜题题目描述：在一个 2x3 的棋盘上，有 5 块编号为 1 到 5 的方块，以及一个空缺（用 0 表示）。谜题的目标是利用这个空缺，通过移动方块，使得棋盘变为目标状态 [[1,2,3],[4,5,0]] 。每次移动可以选择与空缺相邻（上下左右）的一个方块，将其滑入空缺位置。给定一个初始棋盘状态 board ，你需要计算出完成谜题的最少移动次数。如果无法完成，则返回 -1。解题过程：问题分析：这是一个典型的状态搜索问题。每个棋盘布局可以看作图中的一个节点。一次合法的移动（滑动一个与0相邻的方块）相当于在图中从一个节点移动到相邻的节点。我们需要找到从初始状态节点到目标状态节点的最短路径（最少移动次数）。这提示我们使用广度优先搜索（BFS），因为BFS天然地按层（按距离）遍历节点，首次遇到目标状态时，当前的步数就是最短路径。状态表示：直接使用 2x3 的二维数组进行比较和存储效率不高。我们可以将棋盘状态“扁平化”成一个字符串。例如，棋盘 [[1,2,3],[4,0,5]] 可以表示为字符串 "123405" 。使用字符串可以方便地判断状态是否被访问过（使用哈希集合 visited ），并且方便表示目标状态（ "123450" ）。寻找邻居状态（下一步可能的状态）：在BFS的每一步，我们需要从当前状态衍生出所有通过一次移动能得到的新状态。关键点是找到数字 0 在当前字符串中的位置 idx 。根据 idx 的位置，可以确定 0 可以和哪些位置的数字进行交换。我们需要一个映射关系，表示在 2x3 的棋盘上，每个索引位置（0到5）的相邻位置索引。索引布局： 0 1 2 对应第一行， 3 4 5 对应第二行。例如，位置0（第一行第一列）的邻居是位置1（右）和位置3（下）。我们可以预先定义一个邻接表 neighbors ： neighbors[0] = [1, 3] (索引0的邻居是1和3) neighbors[1] = [0, 2, 4] (索引1的邻居是0, 2, 4) neighbors[2] = [1, 5] (索引2的邻居是1和5) neighbors[3] = [0, 4] (索引3的邻居是0和4) neighbors[4] = [1, 3, 5] (索引4的邻居是1, 3, 5) neighbors[5] = [2, 4] (索引5的邻居是2和4) 对于当前状态字符串 s ，找到 '0' 的索引 idx 。遍历 neighbors[idx] 中的每一个邻居索引 neb 。通过交换字符串 s 中 idx 和 neb 位置的字符，就可以得到一个新的状态字符串。 BFS算法步骤：初始化：将初始状态（扁平化后的字符串）加入BFS队列。创建一个已访问集合 visited ，将初始状态加入，防止重复访问。初始化步数 step = 0 。 BFS循环：当队列不为空时，进行循环。我们记录当前队列的大小 size （代表当前“层”的所有节点）。遍历当前层的所有 size 个节点：从队列中取出一个状态 current 。如果 current 等于目标状态 "123450" ，立即返回当前步数 step 。否则，找到 current 中 '0' 的位置 idx 。遍历 idx 的所有邻居索引 neb （从预定义的 neighbors 表中获取）：将字符串 current 转换为字符列表 chars ，以便交换操作。交换 chars[idx] 和 chars[neb] 的值。将交换后的字符列表转换回新的字符串 new_state 。如果 new_state 不在 visited 集合中：将其加入 visited 集合。将其加入BFS队列，等待下一层遍历。当前层的所有节点处理完毕后，步数 step 加 1，表示进入下一层（即移动次数增加一次）。终止：如果BFS循环结束（队列为空）仍未找到目标状态，说明无解，返回 -1。复杂度分析：由于棋盘是 2x3，总的不同状态数是 6 ! (720) 种。这是一个很小的常数。因此，BFS的时间和空间复杂度都可以看作是 O(1)。这个算法通过BFS系统地探索所有可能的状态，利用预定义的邻居关系高效生成新状态，并使用哈希集合避免重复访问，从而在最短的移动次数内找到解或判断无解。