[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