标题：跳蚱蜢

如图 p1.png 所示： 有9只盘子，排成1个圆圈。

其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8。

每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？

注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。

BFS

Python

from collections import deque


def bfs(arr):
    n, vis, queue = len(arr), dict(), deque()
    queue.append((arr, 0))
    while queue:
        front = queue.popleft()
        tmp, cnt = front
        # print(tmp, cnt)

        if tmp == "876543210":
            print(cnt)
            return

        if vis.get(tmp, None):
            continue
        vis[tmp] = True

        idx, tmp = tmp.index("0"), list(tmp)
        for i in [-2, -1, 1, 2]:
            tmp[idx], tmp[(idx + i) % n] = tmp[(idx + i) % n], tmp[idx]
            val = ''.join(tmp)
            if not vis.get(val, None):
                queue.append((val, cnt + 1))
            tmp[idx], tmp[(idx + i) % n] = tmp[(idx + i) % n], tmp[idx]


if __name__ == '__main__':
    """
    [1, 2, 3, 4, 5, 6, 7, 8, 0] -> [8, 7, 6, 4, 4, 3, 2, 1, 0]
    """
    sequence = "123456780"
    bfs(sequence)