[题目描述可以看这里]

解题思路：双向 BFS

• 分别从起点和终点开始 BFS，记录各自状态下的最少步数。两个状态中途相遇时，两个状态的最少步数之和就是答案。

• 因为题目限定最多 20 步，所以从起点和终点开始只需要各走最多 10 步。

• 金字塔数组进入哈希前，要先序列化成字符串。因为给定的金字塔数组不规则，不像华容道的正方形，所以我把字符串反序列化后再移动 0 的位置。这种办法比较易懂，也许存在更直接的数学办法。

• state 记录当前状态，rc 记录 0 的座标，from_start 记录当前状态从 start 开始还是从 end 开始。

import itertools from collections import deque  class Solution:     """     @param a: the number admiral     @return: the number of steps to return to the original state     """     def getSteps(self, a):         start = self.serialize(a)         end = self.serialize([[0], [1,1], [2,2,2], [3,3,3,3], [4,4,4,4,4], [5,5,5,5,5,5]])         start_r, start_c = self.find_zero(a)                  queue = deque([(start, start_r, start_c, True), (end, 0, 0, False)])         distances_from_start, distances_from_end = {start : 0}, {end : 0}                  while queue:             state, r, c, from_start = queue.popleft()             # Meet in the middle             if (from_start and state in distances_from_end) or                  (not from_start and state in distances_from_start):                 return distances_from_start[state] + distances_from_end[state]             # Move to the next state from start / end             for next_state, i, j in self.get_next(state, r, c, from_start, distances_from_start, distances_from_end):                 if from_start:                     distances_from_start[next_state] = distances_from_start[state] + 1                     # Maximum 10 steps from start                     if distances_from_start[next_state] <= 10:                         queue.append((next_state, i, j, from_start))                 else:                     distances_from_end[next_state] = distances_from_end[state] + 1                     # Maximum 10 steps from end                     if distances_from_end[next_state] <= 10:                         queue.append((next_state, i, j, from_start))                  return -1          def get_next(self, state, r, c, from_start, distances_from_start, distances_from_end):         a = self.deserialize(state)         for i, j in [(r - 1, c), (r + 1, c), (r - 1, c - 1), (r + 1, c + 1)]:             if 0 <= i < len(a) and 0 <= j < len(a[i]):                 next_state = self.swap(a, r, c, i, j)                 if (from_start and next_state not in distances_from_start) or                      (not from_start and next_state not in distances_from_end):                     yield next_state, i, j          def swap(self, a, r, c, i, j):         a[r][c], a[i][j] = a[i][j], a[r][c]         ret = self.serialize(a)         a[r][c], a[i][j] = a[i][j], a[r][c]         return ret      def find_zero(self, a):         for r in range(len(a)):             for c in range(len(a[r])):                 if a[r][c] == 0:                     return r, c         return -1, -1      def serialize(self, a):         return "".join(map(str, itertools.chain(*a)))          def deserialize(self, s):         ret = []         index = 0         for i in range(1, 7):             line = []             for j in range(i):                 line.append(s[index + j])             index += i             ret.append(line)         return ret 

大佬有話說 (0)