0773：滑动谜题（1815 分）

2017-02-11 约 450 字预计阅读 1 分钟次阅读

力扣第 773 题

题目

在一个 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] 中每个值都不同

分析

将整个 board 的状态看作顶点，bfs 即可
假设当前 0 在位置 i，可以预处理 i 能转移到的 j，节省时间

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


g = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        A = tuple(x for row in board for x in row)
        Q, vis = deque([(0,A)]), {A}
        while Q:
            w,u = Q.popleft()
            if u==(1,2,3,4,5,0):
                return w
            i = u.index(0)
            A = list(u)
            for j in g[i]:
                A[i], A[j] = A[j], A[i]
                v = tuple(A)
                if v not in vis:
                    Q.append((w+1,v))
                    vis.add(v)
                A[i], A[j] = A[j], A[i]
        return -1

3 ms

目录

0773：滑动谜题（1815 分）

题目

分析

解答