AcWing 845. 八数码-python
原题链接
中等
作者:
四舍五入
,
2022-02-21 21:43:37
,
所有人可见
,
阅读 104
python 代码
from collections import deque
from collections import defaultdict
def bfs(state):
directions = [(-1,0),(0,1),(1,0),(0,-1)]
end = '12345678x'
q = deque([state])
d = defaultdict(int)
d[state] = 0
while q:
t = q.popleft()
if t == end:
return d[t]
k = t.find('x')
x , y = k // 3, k % 3
for direction in directions:
a, b = x + direction[0], y + direction[1]
if a >= 0 and a < 3 and b >= 0 and b < 3:
tlist = list(t)
tlist[a * 3 + b], tlist[k] = tlist[k], tlist[a * 3 + b]
tstr = ''.join(tlist)
if not d[tstr]:
d[tstr] = d[t] + 1
q.append(tstr)
return -1
if __name__ == '__main__':
s = ''.join(input().split())
print(bfs(s))