標題：跳蚱蜢

如圖 p1.png 所示： 有9只盤子，排成1個圓圈。

其中8只盤子內裝著8只蚱蜢，有一個是空盤。

我們把這些蚱蜢順時針編號為 1~8。

每只蚱蜢都可以跳到相鄰的空盤中，也可以再用點力，越過一個相鄰的蚱蜢跳到空盤中。

請你計算一下，如果要使得蚱蜢們的隊形改為按照逆時針排列，并且保持空盤的位置不變（也就是1-8換位，2-7換位,…），至少要經過多少次跳躍？

注意：要求提交的是一個整數，請不要填寫任何多余內容或說明文字。

BFS

Python

from collections import dequedef 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)returnif vis.get(tmp, None):continuevis[tmp] = Trueidx, 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)

總結

以上是生活随笔為你收集整理的2017/Province_C_C++_A/2/跳蚱蜢的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。