1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/sliding-puzzle/description/

2.解题方法

2.1.解题思路

思路1：广度优先搜索

思路2：A*算法（关键理解预估距离）

2.2.解题步骤

广度优先搜索步骤：

• 第一步，预处理。采用col*r+c的对每个格子进行编号，预先使用数组存储每个位置的相邻的位置；并构建获取相邻结点的getNeighbors函数

• 第二步，广度优先搜索

A*算法步骤：

• 第一步，预处理。构建函数getEstimateDist计算两个状态的预估距离；并构建函数获取状态的相邻状态

• 第二步，构建维护变量，并遍历更新维护变量；dists维护各个结点到初始状态的距离

3.解题代码

python3代码

from collections import deque
from heapq import heapify, heappop, heappush

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # 思路2：A*算法（关键理解预估距离）
        # 第一步，预处理。构建函数getEstimateDist计算两个状态的预估距离；并构建函数获取状态的相邻状态
        def getEstimateDist(state1, state2):
            return sum(abs(int(state1[i]) - abs(int(state2[i]))) for i in range(6))
        nextPositions = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
        def getNeighbors(state) -> list:
            ans = []
            stateArr = list(state)
            i = stateArr.index("0")
            for i2 in nextPositions[i]:
                stateArr[i], stateArr[i2] = stateArr[i2], stateArr[i]
                ans.append("".join(stateArr))
                stateArr[i], stateArr[i2] = stateArr[i2], stateArr[i]
            return ans
        # 第二步，构建维护变量，并遍历更新维护变量；dists维护各个结点到初始状态的距离
        initState = "".join(["".join([str(num) for num in row]) for row in board])
        heap = [(0 + getEstimateDist(initState, "123450"), initState)]
        dists = {initState: 0}
        while heap:
            addedDist, state = heappop(heap)
            if state == "123450":
                return dists[state]
            for neigh in getNeighbors(state):
                newDist = dists[state] + 1
                if neigh not in dists or newDist < dists[neigh]:
                    dists[neigh] = newDist
                    heappush(heap, (newDist + getEstimateDist(neigh, "123450"), neigh))
        return -1

    def slidingPuzzle1(self, board: List[List[int]]) -> int:
        # 思路1：广度优先搜索
        # 第一步，预处理。采用col*r+c的对每个格子进行编号，预先使用数组存储每个位置的相邻的位置；并构建获取相邻结点的getNeighbors函数
        nextPositions = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
        def getNeighbors(state) -> list:
            ans = []
            stateArr = list(state)
            i = stateArr.index("0")
            for i2 in nextPositions[i]:
                stateArr[i], stateArr[i2] = stateArr[i2], stateArr[i]
                ans.append("".join(stateArr))
                stateArr[i], stateArr[i2] = stateArr[i2], stateArr[i]
            return ans
        # 第二步，广度优先搜索
        initState = "".join(["".join([str(num) for num in row]) for row in board])
        que = deque([initState])
        visited = set([initState])
        steps = 0
        while que:
            for _ in range(len(que)):
                state = que.popleft()
                if state == "123450":
                    return steps
                for neigh in getNeighbors(state):
                    if neigh not in visited:
                        que.append(neigh)
                        visited.add(neigh)
            steps += 1
        return -1

4.执行结果