滑动谜题
输入：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]]
class SlidingPuzzle:"""773. 滑动谜题https://leetcode.cn/problems/sliding-puzzle/"""def solution(self, board: List[List[int]]) -> int:""":param board::return:"""m, n = len(board), len(board[0])target = '123450'start = ''for i in range(m):for j in range(n):start += str(board[i][j])# BFS算法 框架开始queue = []visited = set()step = 0nei_map = self.generateNeighborMapping(m, n)# 从起点开始BFS搜索queue.append(start)visited.add(start)while queue:sz = len(queue)for i in range(sz):cur = queue.pop(0)if cur == target:return stepidx = 0for _ in cur:if cur[idx] == '0':breakidx += 1for adj in nei_map[idx]:new_board = self.swap(cur, adj, idx)if new_board not in visited:queue.append(new_board)visited.add(new_board)step += 1return -1def generateNeighborMapping(self, m, n):"""给定一个二维m*n数组，返回每个节点的邻居节点，用一维数组表示:param m::param n::return:"""res = []for i in range(m*n):tmp = []# 如果i不是第一列，那么有左侧邻居if i % n != 0:tmp.append(i-1)# 如果i不是最后一列，那么有右侧邻居if i % n != n-1:tmp.append(i+1)# 如果i不是第一行，那么有上侧邻居if i - n >= 0:tmp.append(i-n)# 如果i不是最后一行，那么有下侧邻居if i + n < m*n:tmp.append(i+n)res.append(tmp)return resdef swap(self, cur, idx, adj):cur_arr = list(cur)tmp = cur_arr[idx]cur_arr[idx] = cur_arr[adj]cur_arr[adj] = tmpreturn ''.join(cur_arr)
