[leetcode/lintcode 题解] 阿里巴巴面试题：金字塔

描述
给你一个金字型塔的数列，第一行一个0，第二行两个1……第六行六个5，现在金字塔数字打乱了，你只能移动0这个数字，并且只能左上、右上、左下、右下走，问在20步内能否回到原来状态。

保证输入合法
如果20步内不能回到原状态，就返回-1

在线评测地址：领扣题库官网

样例1
给定 `a=[[1],[2,0],[2,1,2],[3,3,3,3],[4,4,4,4,4],[5,5,5,5,5,5]]` 返回 `3`
[[1],[2,0],[2,1,2],[3,3,3,3],[4,4,4,4,4],[5,5,5,5,5,5]]
3

解释:
一开始，移动到(2,1)
然后,移动到(1,0)
最后,移动到(0,0)

样例2
给定 `a=[[1],[0,1],[2,2,2],[3,3,3,3],[4,4,4,4,4],[5,5,5,5,5,5]]` 返回 `1`
[[1],[0,1],[2,2,2],[3,3,3,3],[4,4,4,4,4],[5,5,5,5,5,5]]
1

解释:
直接移动到(0,0)

解题思路：双向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

更多题解参考：九章官网solution