773. 滑动谜题（Rating 1815）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

773. 滑动谜题

Rating 1815

思路

类似最少xx次数的题目，如果能将每个状态建模为图的节点，各状态间的变换建模为图中节点之间权值为1的边，那么即可通过bfs求得结果。

本题则是需要维护一个mat交换0与周围值位置前后的状态。

矩阵本身并不好hash，因此考虑将矩阵编码为独一无二的状态。

这里既可以将矩阵编码为字符串，也可以将矩阵编码为一个十进制数字。

此处考虑编码为十进制数字。

代码

import collections

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        def mat2num(mat: List[List[int]]) -> int: # 将矩阵编码为十进制数字
            num = 0
            for i in range(2):
                for j in range(3):
                    num = 10 * num + mat[i][j]
            return num

        def num2mat(num: int) -> List[List[int]]: # 将十进制数字解码为矩阵
            mat = [[0 for _ in range(3)] for _ in range(2)]
            for i in range(2 - 1, -1, -1):
                for j in range(3 - 1, -1, -1):
                    mat[i][j] = num % 10
                    num = num // 10
            return mat

        def find_zero(mat: List[List[int]]) -> (int, int): # 查找mat中0的位置
            for i in range(2):
                for j in range(3):
                    if mat[i][j] == 0:
                        return i, j
            return -1, -1

        dir = [-1, 0, 1, 0, -1] # 上下左右四个方向list
        state = mat2num(board)
        q = collections.deque() # 经典bfs模板
        q.append(state)
        vis = set()
        vis.add(state)
        ret = 0
        while q:
            sz = len(q)
            while sz:
                sz -= 1
                s = q.popleft()
                if s == 123450: # 目标状态编码
                    return ret
                mat = num2mat(s)
                i, j = find_zero(mat)
                for d in range(4):
                    x, y = i + dir[d], j + dir[d + 1]
                    if x < 0 or x >= 2 or y < 0 or y >= 3:
                        continue
                    mat[i][j], mat[x][y] = mat[x][y], mat[i][j] # 交换0与其周围值的位置
                    nxts = mat2num(mat)
                    if nxts not in vis:
                        q.append(nxts)
                        vis.add(nxts)
                    mat[i][j], mat[x][y] = mat[x][y], mat[i][j] # 恢复回来
            ret += 1
        return -1