题目描述
八数码问题
样例
其实就是最强大脑这个节目玩的回容道游戏
输入样例:
2 3 4 1 5 x 7 6 8
输出:
19
算法1
(广度优先搜索) $O(树的节点个数)$
记录’x’位置,将初始状态看成一个节点,然后将x与上下左右交换,将新状态看成新节点,即宽搜。
然后不能重复搜索一个状态, 我是用将列表转成元组,并放到字典中标记。 c++可以将新状态转成一个字符串,如 “12x345678”,然后放到unordered_map中标记,标记这种情况已经被使用过了。
时间复杂度分析:blablabla
python 代码
from collections import deque
from copy import copy
tmp = raw_input().split()
start = tmp.index('x')
def check(a):
return a == ['1','2','3','4','5','6','7','8','x']
q = deque()
visited = dict()
visited[tuple(tmp)] = True
q.append((tmp, start))
move = 0
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
flag = False
while q and not flag:
for i in range(len(q)):
node, start = q.popleft()
if start==8:
if check(node):
print move
flag = True
break
row, col = start // 3, start % 3;
for j in range(4):
new_row, new_col = row + dx[j], col + dy[j]
if 0<=new_row<3 and 0<=new_col<3:
tmp = copy(node);
new_start = new_row*3 + new_col;
tmp[new_start], tmp[start] = tmp[start], tmp[new_start]
k = tuple(tmp)
if k not in visited:
visited[k] = True
q.append((tmp, new_start))
move += 1
if not flag:
print -1
寿比南山