773. 滑动谜题

在一个 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] 的排列.

bfs 困难 每日一题

和0752.打开转盘锁 差不多的解法，把二维数组展成一维更好算一些

代码

1. 我用二维数组硬写的：

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        target = [[1,2,3],[4,5,0]]
        if board == [[1,2,3],[4,5,0]]: 
            return 0
        try:
            x = 0
            y = board[0].index(0)
        except:
            x = 1
            y = board[1].index(0)
        queue = [(board,0,x,y)]
        visited = set()
        while queue:
            cur, step, x, y = queue.pop(0)
            next_status = []
            # 开始构造下一可能状态
            if y < 2: # 0 不在右边界就能向右移
                cur[x][y+1], cur[x][y] = cur[x][y], cur[x][y+1]
                next_status.append((copy.deepcopy(cur),x,y+1))
                # 再移回去
                cur[x][y+1], cur[x][y] = cur[x][y], cur[x][y+1]
            if y > 0: # 0 不在左边界就能向左移
                cur[x][y-1], cur[x][y] = cur[x][y], cur[x][y-1]
                next_status.append((copy.deepcopy(cur),x,y-1))
                # 再移回去
                cur[x][y-1], cur[x][y] = cur[x][y], cur[x][y-1]

            cur[1][y], cur[0][y] = cur[0][y], cur[1][y]
            next_status.append((copy.deepcopy(cur),(x+1)%2,y))
            # 再移回去
            cur[1][y], cur[0][y] = cur[0][y], cur[1][y]
            # 所有构造完毕
            
            for status,x,y in next_status:
                if str(status) not in visited:
                    if status == target: 
                        return step +1
                    queue.append((status,step+1,x,y))
                    visited.add(str(status))
        return -1

2. 展开的方法

class Solution:
    NEIGHBORS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]

    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # 枚举 status 通过一次交换操作得到的状态
        def get(status: str) -> Generator[str, None, None]:
            s = list(status)
            x = s.index("0")
            for y in Solution.NEIGHBORS[x]:
                s[x], s[y] = s[y], s[x]
                yield "".join(s)
                s[x], s[y] = s[y], s[x]

        initial = "".join(str(num) for num in sum(board, []))
        if initial == "123450":
            return 0

        q = deque([(initial, 0)])
        seen = {initial}
        while q:
            status, step = q.popleft()
            for next_status in get(status):
                if next_status not in seen:
                    if next_status == "123450":
                        return step + 1
                    q.append((next_status, step + 1))
                    seen.add(next_status)
        
        return -1