773. 滑动谜题

题目描述

数字华容道，只有6个数字
问把0换到最后最少需要多少步？

基本分析

1. bfs的时候，当前状态怎么表示？把矩阵拉平，变成字符串
2. 怎么快速可以得到某个字符串可以变成哪些字符串？(1)怎么快速知道不同情况下0周围的索引？枚举余处理（2）怎么知道不同mask对应的可产生的mask？在以上基础上定义函数实现
3. bfs的时候怎么入队和去重？入队的内容是mask，用vis数组去重

代码

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        mp = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]

        def getnei(mask):
            ans = []
            ls = list(mask)
            i = ls.index('0')
            for j in mp[i]:
                ls[j], ls[i] = ls[i], ls[j]
                ans.append(''.join(ls))
                ls[j], ls[i] = ls[i], ls[j]
            return ans
        
        start_mask = "".join(str(i) for i in sum(board, []))
        if start_mask == "123450":
            return 0

        q = deque([start_mask])
        vis = {start_mask}
        step = 0

        while q:
            step += 1
            for _ in range(len(q)):
                cur_mask = q.popleft()
                for nxt_mask in getnei(cur_mask):
                    if nxt_mask == "123450":
                        return step
                    if not nxt_mask in vis:
                        vis.add(nxt_mask)
                        q.append(nxt_mask)
        
        return -1

总结

1. 这里有其他数字，不考虑2进制压缩，而是直接拉平变成字符串，利用字符串的特性进行哈希。
2. 枚举mask可以产生哪些新的mask时候，这里是直接返回了所有结果；也可以写成yield的形式。
3. 在入队之前就需要判断一下mask，看是不是已经满足要求