1426: 蓝桥杯历届试题-九宫重排（Python3）

解题思路:
    同1878题。

注意事项:
    此题不能用二维数组表示状态（注释部分），会超时。

参考代码:

def bfs():
    global start, end, cache_state
    stack = [start]
    while stack:
        state = stack.pop(0)
        for direction in around:
            i, j = divmod(state.index('.'), 3)
            if 0 <= i + direction[0] < 3 and 0 <= j + direction[1] < 3:
                # temp = [list(state[3 * k:3 * k + 3]) for k in range(3)]
                # temp[i][j], temp[i + direction[0]][j + direction[1]] = temp[i + direction[0]][j + direction[1]], temp[i][j]
                # temp = ''.join(element for row in temp for element in row)
                temp = list(state)
                idx_0, idx_1 = 3 * i + j, 3 * (i + direction[0]) + j + direction[1]
                temp[idx_0], temp[idx_1] = temp[idx_1], temp[idx_0]
                temp = ''.join(temp)
                if temp not in cache_state:
                    cache_state.setdefault(temp, cache_state[state] + 1)
                    stack.append(temp)
                    if temp == end:
                        return cache_state[end]

                        
start, end = [input().strip() for _ in range(2)]
cache_state, around = {start: 0}, [[-1, 0], [0, -1], [1, 0], [0, 1]]
print(bfs())