Python 代码
from collections import deque
q = deque()
d = {}
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
def check(x, y):
if 0 <= x < 3 and 0 <= y < 3:
return True
else:
return False
def bfs(s):
end = "12345678x"
q.append(s)
d[s] = 0
while q:
t = q.popleft()
dist = d[t]
if t == end: return dist
k = t.index('x')
x, y = k // 3, k % 3
for i in range(4):
xx, yy = x + dx[i], y + dy[i]
t = list(t)
if check(xx, yy):
t[k], t[xx * 3 + yy] = t[xx * 3 + yy], t[k]
if ''.join(t) not in d:
d[''.join(t)] = dist + 1
q.append(''.join(t))
t[k], t[xx * 3 + yy] = t[xx * 3 + yy], t[k]
return -1
s = input().split()
s = ''.join(s)
print(bfs(s))