求解从矩阵A转换到矩阵B的最少相邻交换步数（仅与0交换）

现有2×3的基础矩阵A：

A = 
0 1 2
3 4 5

需要找到转换为目标矩阵B的最少步数，示例目标矩阵B如下：

B =
1 2 5
3 4 0

转换规则：仅能与0**相邻（上下左右方向）**的数字进行交换。示例中需依次将0与1、2、5交换，共3步。

想基于DFS算法实现，但不清楚具体步骤，寻求解决方法。

DFS（深度优先搜索）通过沿着路径深入搜索，回溯后尝试其他分支来遍历所有可能状态，要实现找最少步数的需求，需要结合状态记录和剪枝优化，具体步骤如下：

1. 矩阵状态的简化表示 #

为了方便存储、比较和传递矩阵状态，将2×3的矩阵转换为字符串或一维数组。比如初始矩阵A可表示为"012345"，目标矩阵B表示为"125340"，判断状态是否匹配只需直接比较字符串即可。

2. 记录已访问状态 #

用集合存储已经处理过的矩阵状态，避免重复遍历相同状态，防止无限循环和冗余计算。

3. 定位0的位置 #

对于任意状态，先找到0的位置：

• 若用字符串表示，通过index('0')获取0的索引
• 将索引转换为矩阵坐标：行号 = 索引 // 3，列号 = 索引 % 3

4. 生成合法的相邻状态 #

根据0的坐标，遍历上下左右四个方向，判断是否在矩阵边界内（行号0_1，列号02）：

• 上：行号-1 ≥ 0
• 下：行号+1 < 2
• 左：列号-1 ≥ 0
• 右：列号+1 < 3
  对每个合法方向，交换0与相邻元素的位置，生成新的状态字符串。

5. 递归式DFS实现 #

递归函数核心逻辑：

• 剪枝：如果当前步数已经大于等于已知的最小步数，直接回溯，无需继续搜索
• 终止条件：如果当前状态等于目标状态，更新全局最小步数
• 标记访问：将当前状态加入已访问集合
• 遍历分支：对每个合法的新状态，若未被访问则递归调用DFS，步数+1
• 回溯：递归返回后，将当前状态从已访问集合中移除，保证其他路径可再次访问该状态

6. 剪枝优化 #

初始时将最小步数设为无穷大，一旦找到一个可行解，后续所有步数大于等于该值的路径都可以直接跳过，大幅减少无效搜索。

start_state = "012345"
target_state = "125340"
min_steps = float('inf')
visited = set()

# 定义四个移动方向：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def dfs(current, steps):
    global min_steps
    # 剪枝：当前步数已超过已知最小值，无需继续
    if steps >= min_steps:
        return
    # 到达目标状态，更新最小步数
    if current == target_state:
        min_steps = steps
        return
    # 标记当前状态已访问
    visited.add(current)
    # 找到0的位置
    zero_idx = current.index('0')
    row = zero_idx // 3
    col = zero_idx % 3
    # 遍历所有可能的移动方向
    for dr, dc in directions:
        new_row = row + dr
        new_col = col + dc
        # 检查是否在矩阵范围内
        if 0 <= new_row < 2 and 0 <= new_col < 3:
            neighbor_idx = new_row * 3 + new_col
            # 交换0和相邻元素，生成新状态
            current_list = list(current)
            current_list[zero_idx], current_list[neighbor_idx] = current_list[neighbor_idx], current_list[zero_idx]
            new_state = ''.join(current_list)
            # 未访问过的状态才继续递归
            if new_state not in visited:
                dfs(new_state, steps + 1)
    # 回溯：移除当前状态，允许其他路径访问
    visited.remove(current)

# 启动DFS搜索
dfs(start_state, 0)
print(f"最少转换步数：{min_steps}")

DFS虽然能解决问题，但BFS（广度优先搜索）更适合最短路径问题——因为BFS按层遍历，第一次到达目标状态的步数就是最少步数，无需遍历所有长路径，效率更高。如果对性能有要求，优先考虑BFS实现。

内容的提问来源于stack exchange，提问作者popcorn