题目 1426: [蓝桥杯][历届试题]九宫重排

问题分析

九宫格，一个空格，8个数字，给定初态、终态

找到初态变换到终态需要移动的最小步数

输出步数，如果不可达输出-1

解题思路

① 分解子问题

\[\left[ \begin{matrix} 1\quad2\quad3 \\ .\quad4\quad6 \\ 7\quad5\quad8 \\ \end{matrix} \right] \begin{cases} \left[ \begin{matrix} .\quad2\quad3 \\ 1\quad4\quad6 \\ 7\quad5\quad8 \\ \end{matrix} \right] \begin{cases} ... \\ ... \\ \end{cases} \\ \\ \left[ \begin{matrix} 1\quad2\quad3 \\ 4\quad.\quad6 \\ 7\quad5\quad8 \\ \end{matrix} \right] \begin{cases} ... \\ ... \\ ... \\ ... \\ \end{cases}\\ \\ \left[ \begin{matrix} 1\quad2\quad3 \\ 7\quad4\quad6 \\ .\quad5\quad8 \\ \end{matrix} \right] \begin{cases} ... \\ ... \\ \end{cases} \end{cases} \]

② 是否具有最优子结构

具有，但不好描述子问题之间的关系（非线性=>一般需要设置访问记录表，如果是线性自然就不会重复）

③ 寻找最小步数的过程，即为逐层分解的过程出现的第一个解

使用广度优先搜索BFS

队列中存放九宫格的状态(字符串形式的九宫格)和从初态到达该状态所需的步数

访问记录字典中存放bool值

结束条件：当前状态与终态相同，输出步数

代码

from queue import Queue
start = input()
end = input()
def next_state(curr, i):
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    bi = curr.index('.')
    newr, newc = dr[i] + bi//3, dc[i] + bi%3
    if 0 <= newr < 3 and 0 <= newc < 3:
        ni = newr*3+newc
        curr = list(curr)
        curr[bi], curr[ni] = curr[ni], curr[bi]
        return ''.join(curr)
    return None
def bfs(start):
    sq = Queue()
    sq.put([start, 0])
    visits = {}
    while not sq.empty():
        curr, step = sq.get()
        for i in range(4):
            if curr == end:
                return step
            next = next_state(curr, i)
            if next and not visits.get(next):
                visits[next] = True
                sq.put([next, step + 1])
    return -1
print(bfs(start))