蓝桥杯-九宫重排

这道题一眼BFS，求最短路径问题。所以写了最优解一坨屎山！


import sys
from collections import deque

# 读取初始状态和目标状态字符串
s = input()
target = input()

# 初始化起始位置（空格'.'的位置）
start_x = 0
start_y = 0

# 创建 3x3 的网格表示
grid = [[''] * 3 for _ in range(3)]
target_grid = [[''] * 3 for _ in range(3)]

# 将输入字符串转换为 3x3 网格，并记录空格位置
k = 0
for i in range(3):
    for j in range(3):
        grid[i][j] = s[k]
        if grid[i][j] == '.':  # 找到空格位置
            start_x = i
            start_y = j
        k += 1

# 将目标字符串转换为 3x3 网格
k = 0
for i in range(3):
    for j in range(3):
        target_grid[i][j] = target[k]
        k += 1

# 将网格转换为字符串，便于存储和比较
def grid_to_string(g):
    return ''.join(''.join(row) for row in g)

# 目标状态的字符串表示
target_str = grid_to_string(target_grid)

# BFS 初始化
vis = set()  # 记录已访问的状态，避免重复搜索
q = deque([(start_x, start_y, 0, grid_to_string(grid))])  # (空格 x 坐标，空格 y 坐标，步数，当前状态)
vis.add(grid_to_string(grid))  # 标记初始状态为已访问

# 四个方向：下、上、右、左
di = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# BFS 主循环
while q:
    # 遍历当前层的所有状态
    for _ in range(len(q)):
        x, y, steps, state_str = q.popleft()  # 取出队首状态

        # 将状态字符串转换回 3x3 网格
        current = [list(state_str[i:i+3]) for i in range(0, 9, 3)]

        # 尝试向四个方向移动空格
        for dx, dy in di:
            nx, ny = x + dx, y + dy  # 计算新的空格位置
            # 检查新位置是否在边界内
            if 0 <= nx < 3 and 0 <= ny < 3:
                # 交换空格和相邻位置的字符（模拟滑动）
                current[x][y], current[nx][ny] = current[nx][ny], current[x][y]
                new_state = grid_to_string(current)  # 获取新状态的字符串表示

                # 如果达到目标状态，输出步数并退出
                if new_state == target_str:
                    print(steps + 1)
                    sys.exit(0)
                
                # 如果新状态未访问过，加入队列继续搜索
                if new_state not in vis:
                    vis.add(new_state)
                    q.append((nx, ny, steps + 1, new_state))
                
                # 回溯：恢复原状态，以便尝试下一个方向
                current[x][y], current[nx][ny] = current[nx][ny], current[x][y]

看来站长很喜欢写屎山。。。