1878: 蓝桥杯2017年第八届真题-青蛙跳杯子（Python3）BFS

解题思路:
    1.BFS遍历所有状态，储存状态及其对应的步数；

    2.发现和结果吻合则退出。

注意事项:
    1.使用字典存储某一状态和对应步数，便于查找重复状态，降低时间复杂度；

    2.不要使用列表存储状态，因为列表不能作为字典键值，而应用字符串；

    3.“跳杯”的过程可以用列表实现。

参考代码:

def bfs():
    global start, end, cache_state, around
    stack = [start]
    while stack:
        temp_state = stack.pop(0)
        idx = temp_state.index('*')
        for i in around:
            if 0 <= idx + i < len(start) and temp_state[idx + i] != '*':
                temp = list(temp_state)
                temp[idx], temp[idx + i] = temp[idx + i], temp[idx]
                a = "".join(temp)
                if a not in cache_state:
                    cache_state.setdefault(a, cache_state[temp_state] + 1)
                    stack.append(a)
                    if a == end:
                        return cache_state[a]


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