day1， 第二道

题目描述

如图所示： 有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。 请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？

输出

输出一个整数表示答案

题目分析

题目初始状态：012345678， 最终目标：087654321

看成空盘跟自己左右两边的四个盘子中的任意一个交换位置。

题解

采用BFS优先遍历，把每次的结果都存入dict中，然后跑，用Python是真滴慢~~

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#!/usr/bin/env python
# -*- coding: utf-8 -*-


result_dict = dict()
result_dict['012345678'] = 0

# 交换 两个
def swap(s: str, i: int):
    center = s.index('0')
    swap_index = (center + i) % len(s)
    result = []
    result.extend(s)
    result[center] = result[swap_index]
    result[swap_index] = '0'
    result = ''.join(result)
    result_dict[result] = result_dict.get(s, 0) + 1


i = 0
while True:
    
    if '087654321' in result_dict.keys():
        print(result_dict['087654321'])
        break
    else:
        temp = list(result_dict.keys())[i]
        swap(temp, 1)
        swap(temp, -1)
        swap(temp, 2)
        swap(temp, -2)
    i += 1
    if i % 100 == 0:
        print(result_dict)