题目描述
数字华容道，只有6个数字
问把0换到最后最少需要多少步？
| f1-构建状态表示的mask + bfs |
基本分析
- bfs的时候，当前状态怎么表示？把矩阵拉平，变成字符串
- 怎么快速可以得到某个字符串可以变成哪些字符串？(1)怎么快速知道不同情况下0周围的索引？枚举余处理（2）怎么知道不同mask对应的可产生的mask？在以上基础上定义函数实现
- 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
总结
- 这里有其他数字，不考虑2进制压缩，而是直接拉平变成字符串，利用字符串的特性进行哈希。
- 枚举mask可以产生哪些新的mask时候，这里是直接返回了所有结果；也可以写成yield的形式。
- 在入队之前就需要判断一下mask，看是不是已经满足要求