AcWing 845. 八数码-python3

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 845. 八数码-python3 原题链接中等

作者：

机械佬也想学编程 , 2020-07-08 00:33:07 , 所有人可见 , 阅读 1871

12

5

from collections import deque


def bfs(start):
    end = "12345678x"
    d = {start : 0} # 该字典存放每个状态距离初始状态的距离
    q = deque() # 存放将要验证的状态
    q.append(start)
    dx = [0, 1, 0, -1] # 用于"x"上下左右移动
    dy = [1, 0, -1, 0]
    while q:
        t = q.popleft()
        distance = d[t]
        if t == end:
            return distance
        k = t.index('x')
        x = k // 3 # 字符串的索引转换成3x3矩阵后的坐标
        y = k % 3

        tl = list(t) # 由于字符串不是不可变量，因而把字符串变为数组，用于交换字符串中的字符位置
        for i in range(4): # "x"上下左右移动
            a = x + dx[i]
            b = y + dy[i]
            if a >=0 and a < 3 and b >=0 and b < 3: # 若坐标未超出矩阵范围
                nk = a * 3 + b #3x3矩阵的坐标转换成字符串的索引
                tl[nk], tl[k] = tl[k], tl[nk] # 交换字符串中的字符位置
                t = "".join(tl)
                if t not in d: # 如果t这个状态是新状态(之前未出现过)
                    q.append(t)
                    d[t] = distance + 1
                tl[nk], tl[k] = tl[k], tl[nk] # 还原现场
    return -1



start = input().replace(" ", "")
ans = bfs(start)
print(ans)

8 评论

渝_3 2022-03-05 08:23

作者大大我想问下，可不可以用我下面的方式模拟栈，，还有我的程序输出答案有误能帮忙看一下么？感谢~~~

def bfs(h):
    end = '12345678x'
    q = [h]
    d = {h:0}

    dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
    while len(q):
        t = q[-1]
        q.pop() # 使用append和pop函数从尾部模拟栈

        distence = d[t]
        if t == end: return distence

        # 状态转移
        k = t.find('x') # 先找到x的下标
        x, y = k//3, k%3 # 找到x的横纵坐标（小技巧，理解）

        s = list(t)
        for i in range(4): # 和四个方向交换位置
            a = x + dx[i]
            b = y + dy[i]
            if a>=0 and a<3 and b>=0 and b<3: # 保证变换后没有越界
                j = a*3 + b
                s[k], s[j] = s[j], s[k]
                t = ''.join(s)
                if t not in d: # 如果当前更新完之后的t之前没有搜到过
                    #(之前搜到过说明之前的路径更短，可以舍去这一条路径)
                    d[t] = distence + 1
                    q.append(t)
                s[k], s[j] = s[j], s[k]
    return -1

start = input().replace(' ', '')
ans = bfs(start)
print(ans)