官方链接
https://leetcode-cn.com/problems/sliding-puzzle
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：
输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板输入：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 = [[3,2,4],[1,5,0]]
输出：14提示：
board 是一个如上所述的 2 x 3 的数组.
board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.
思路
DFS BFS A*
花花酱 8 Puzzles
<https://zxi.mytechroad.com/blog/searching/8-puzzles- bidirectional-astar-vs-bidirectional-bfs/>
解法一
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
# 方向变换向量。类似四联通图，八联通图
moves = {
0: [1, 3], # 当零位于第零个位置的时候，可以移动到第一个和第三个位置
1: [0, 2, 4],
2: [1, 5],
3: [0, 4],
4: [1, 3, 5],
5: [2, 4]
}
used = set()
cnt = 0
s = "".join(str(c) for row in board for c in row) # 把二维的数组转成一维的字符串
q = [s] # 123405
while q:
new = []
for s in q:
used.add(s)
if s == "123450":
return cnt
arr = [c for c in s]
# 开始移动 0
zero_index = s.index('0') # 因为只能变换零，所以要先找到零的位置
for move in moves[zero_index]:
new_arr = arr[:] # 复制一份
new_arr[zero_index], new_arr[move] = new_arr[move], new_arr[zero_index] # 将 move index 和 zero_index 交换
new_s = "".join(new_arr)
if new_s not in used:
new.append(new_s)
cnt += 1
q = new
return -1
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
board = board[0] + board[1] # 把 board 连起来变一维
moves = [(1, 3), (0, 2, 4), (1, 5), (0, 4), (1, 3, 5), (2, 4)] # 每个位置的 0 可以交换的位置, 第 0 个位置可以和 1, 3 交换
q, visited = [(tuple(board), board.index(0), 0)], set() # bfs 队列和已访问状态记录, q (board, 0 的位置, 挪的步数)
while q:
state, now, step = q.pop(0) # 分别代表 当前状态, 0 的当前位置 和 当前步数
if state == (1, 2, 3, 4, 5, 0): # 找到了
return step
for next in moves[now]: # 遍历所有交换位置
_state = list(state)
_state[next], _state[now] = _state[now], _state[next] # 交换位置
_state = tuple(_state)
if _state not in visited: # 确认未访问
q.append((_state, next, step+1))
visited.add(state)
return -1
解法二
A*