滑动谜题

难度: Hard

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

示例 1：

输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成

示例 2:

输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板

示例 3:

输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]

提示：

board.length == 2
board[i].length == 3
0 <= board[i][j] <= 5
board[i][j] 中每个值都不同

Submission

运行时间: 28 ms

内存: 0.0 MB

class Solution:
    NEIGHBORS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]

    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # 枚举 status 通过一次交换操作得到的状态
        def get(status: str) -> Generator[str, None, None]:
            s = list(status)
            x = s.index("0")
            for y in Solution.NEIGHBORS[x]:
                s[x], s[y] = s[y], s[x]
                yield "".join(s)
                s[x], s[y] = s[y], s[x]

        initial = "".join(str(num) for num in sum(board, []))
        if initial == "123450":
            return 0

        q = deque([(initial, 0)])
        seen = {initial}
        while q:
            status, step = q.popleft()
            for next_status in get(status):
                if next_status not in seen:
                    if next_status == "123450":
                        return step + 1
                    q.append((next_status, step + 1))
                    seen.add(next_status)
        
        return -1

Explain

本题解采用广度优先搜索（BFS）来解决滑动谜题。首先，将二维数组board转换为一维状态字符串，例如[[1,2,3],[4,0,5]]转化为'123405'。设定目标状态为'123450'。使用队列q来存储每一步的状态及其对应的移动次数，同时使用集合seen来记录已经访问过的状态，避免重复处理。对于当前状态，通过交换0与其相邻位置的数字来生成新的状态，并检查是否已达到目标状态或是否已被访问过。若达到目标状态，则返回对应的移动次数。如果队列被耗尽还未找到目标状态，则返回-1表示无法解开谜题。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    NEIGHBORS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]

    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # 枚举 status 通过一次交换操作得到的状态
        def get(status: str) -> Generator[str, None, None]:
            s = list(status)
            x = s.index(\"0\")
            for y in Solution.NEIGHBORS[x]:
                s[x], s[y] = s[y], s[x]
                yield \"\".join(s)
                s[x], s[y] = s[y], s[x]

        initial = \"\".join(str(num) for num in sum(board, []))
        if initial == \"123450\":
            return 0

        q = deque([(initial, 0)])
        seen = {initial}
        while q:
            status, step = q.popleft()
            for next_status in get(status):
                if next_status not in seen:
                    if next_status == \"123450\":
                        return step + 1
                    q.append((next_status, step + 1))
                    seen.add(next_status)
        
        return -1

Explore

广度优先搜索（BFS）是解决此类最短路径或最少步骤问题的首选算法，因为它按层次遍历所有状态，确保一旦找到目标状态，此路径即为最短路径。相比之下，深度优先搜索（DFS）可能会首先探索较深的路径，导致找到的可能不是最短路径。此外，在具有大量状态的问题中，DFS可能会导致过深的递归，而BFS更易于管理和实现。

在BFS算法中，使用一个集合（在题解中是`seen`）来记录已经访问过的状态。每次生成新状态时，会检查该状态是否已存在于集合中。如果已存在，表明该状态已被处理过，因此跳过以避免重复工作和不必要的计算。这样做不仅节省了资源，还能防止无限循环。

`get`函数中首先将状态字符串转为列表，并找出0的位置索引。使用`NEIGHBORS`数组可以快速查找0可以交换的位置。这个数组是根据0在一维数组中的位置预先定义的，描述了可能的交换位置。例如，如果0在位置1，它可以与位置0、2、4的元素交换。选择使用这种数组是因为它简化了查找过程并提高了效率，避免了在每次交换时重新计算邻居位置。

如果初始状态已经是目标状态，这意味着不需要任何移动就已达到目标。在这种情况下，返回0是因为从初始状态到目标状态的最短路径长度为0，即不需要任何步骤。继续执行搜索过程将是不必要的，因为我们已经处于解决方案状态。