LeetCode 题解工作台
滑动谜题
在一个 2 x 3 的板上（ board ）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换. 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。 给出一个谜板的初始状态 board …
6
题型
3
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def slidingPuzzle(self, board: List[List[int]]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
在一个 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 == 2board[i].length == 30 <= board[i][j] <= 5board[i][j]中每个值都 不同
解题思路
方法一
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
t = [None] * 6
def gets():
for i in range(2):
for j in range(3):
t[i * 3 + j] = str(board[i][j])
return ''.join(t)
def setb(s):
for i in range(2):
for j in range(3):
board[i][j] = int(s[i * 3 + j])
def f():
res = []
i, j = next((i, j) for i in range(2) for j in range(3) if board[i][j] == 0)
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < 2 and 0 <= y < 3:
board[i][j], board[x][y] = board[x][y], board[i][j]
res.append(gets())
board[i][j], board[x][y] = board[x][y], board[i][j]
return res
start = gets()
end = "123450"
if start == end:
return 0
vis = {start}
q = deque([(start)])
ans = 0
while q:
ans += 1
for _ in range(len(q)):
x = q.popleft()
setb(x)
for y in f():
if y == end:
return ans
if y not in vis:
vis.add(y)
q.append(y)
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O((m * n)! * (m * n)) because each unique board state is visited once and generating neighbors takes O(m * n). Space complexity is O((m * n)!) due to storing all visited states. |
| 空间 | O((m \cdot n)!) |
面试官常问的追问
外企场景- question_mark
Candidate tries BFS but does not track visited states.
- question_mark
Candidate fails to map 0's neighbors efficiently, slowing traversal.
- question_mark
Candidate confuses solvable and unsolvable board configurations.
常见陷阱
外企场景- error
Not memoizing visited boards leads to exponential runtime.
- error
Swapping tiles incorrectly due to wrong index mapping.
- error
Returning a move count for unsolvable boards instead of -1.
进阶变体
外企场景- arrow_right_alt
Generalize to m x n sliding puzzles for larger boards using the same BFS + DP approach.
- arrow_right_alt
Return the actual sequence of moves that solves the puzzle, not just the count.
- arrow_right_alt
Use A* search with Manhattan distance heuristic instead of pure BFS to optimize performance.