845. 八数码
摘要
Title: 845. 八数码
Tag: BFS
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
845. 八数码
-
题意
见原题
-
思路
注意:
- 通过字符串来记录每一次的状态
- 这样获取某一个元素的二维坐标, n代表行数, m代表列数
- x = id // n
- y = id % m
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40'''
Author: NEFU AB-IN
Date: 2022-03-02 16:49:23
FilePath: \ACM\Acwing\845.py
LastEditTime: 2022-03-02 17:20:48
'''
from collections import Counter, deque
d = Counter()
def bfs(start):
q = deque()
q.appendleft(start)
end = '12345678x'
while q:
t = q.pop()
if t == end:
return d[t]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
id = t.index('x')
x, y = id // 3, id % 3
for i in range(4):
x1 = x + dx[i]
y1 = y + dy[i]
tmp = list(t)
if x1 >= 0 and x1 < 3 and y1 >= 0 and y1 < 3:
tmp[id], tmp[x1 * 3 + y1] = tmp[x1 * 3 + y1], tmp[id]
tmp = "".join(tmp)
if not d[tmp]:
q.appendleft(tmp)
d[tmp] = d[t] + 1
return -1
start = "".join(input().split())
print(bfs(start))