from collections import deque
def to_string(grid):
ans = ''
for i in range(3):
for j in range(3):
ans += grid[i][j]
return ans
def to_grid(s):
grid = []
grid.append([s[0], s[1], s[2]])
grid.append([s[3], s[4], s[5]])
grid.append([s[6], s[7], s[8]])
return grid
def bfs(init_grid):
que = deque()
visit = set()
key = to_string(init_grid)
flag = False
for i in range(3):
for j in range(3):
if grid[i][j] == 'x':
pos_i, pos_j = i, j
flag = True
break
if flag:
break
que.append( (key, pos_i, pos_j) )
visit.add(key)
step = 0
while len(que) > 0:
node_num = len(que)
for _ in range(node_num):
key, i, j = que.popleft()
if key == '12345678x':
return step
for ii, jj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
if ii >= 0 and ii < 3 and jj >= 0 and jj < 3:
new_grid = to_grid(key)
new_grid[ii][jj], new_grid[i][j] = new_grid[i][j], new_grid[ii][jj]
new_key = to_string(new_grid)
if new_key not in visit:
visit.add(new_key)
que.append((new_key, ii, jj))
step += 1
return -1
arr = input().split()
grid = [arr[0:3], arr[3:6], arr[6:]]
print(bfs(grid))
下次多一点思路更好哦!