这道算法题怎么解?

Question

有一个由 n x n 个格子组成的正方形,除了其中一个格子是空外,其余格子都放置了一个数字,数字从 1 到 n x n - 1,然后通过移动数字,让数字从左到右从上到下按顺序排列,空的格子会在右下角。

求实现目标的最小步骤数,并列出所有步骤。一个步骤中在一个方向上可以移动多个数字,步骤格式使用
[空格子位置, 移动方向, 移动数字个数] 表示

移动方向有 rtl, ltr, ttb, btt 四种。

例如对于 3 x 3 的情况

[
  [3, 4 , 5],
  [7, 8,  _],
  [1, 2, 6]
]

那么下一步的步骤可以是:
[[1, 2], 'ltr', 1],
[[1, 2], 'ltr', 2],
[[1, 2], 'ttb', 1],
[[1, 2], 'btt', 1] 中的一种。

现在给出一个二维数组,其中空的格子使用 0 表示,然后获取最小步骤数和实现的步骤列表。

Answer 1

from collections import deque
directions = {'rtl': (-1, 0), 'ltr': (1, 0), 'ttb': (0, -1), 'btt': (0, 1)}

def min_steps_to_sort(matrix):
    n = len(matrix)
    target = [[i for i in range(1, n*n)] + [0]]

    # 将矩阵转换为易于处理的表示形式
    initial_state = flatten_matrix(matrix)

    queue = deque([(initial_state, [])])
    visited = set()

    while queue:
        state, steps = queue.popleft()
        if state == target:
            return steps

        for pos in find_zero(state):  # 寻找当前状态下的空格子位置
            x, y = pos
            for direction, (dx, dy) in directions.items():
                new_pos = (x + dx, y + dy)
                if 0 <= new_pos[0] < n and 0 <= new_pos[1] < n:
                    new_state = move_zeros(state, pos, new_pos)
                    if new_state not in visited:
                        visited.add(new_state)
                        queue.append((new_state, steps + [(pos, direction, count_zeros_in_direction(state, pos, direction))]))

    return None  # 如果无法到达目标状态，则返回None

# 辅助函数：将矩阵展平为一维数组
def flatten_matrix(matrix):
    ...

# 辅助函数：查找矩阵中0的位置
def find_zero(state):
    ...

# 辅助函数：将空格子从一个位置移动到另一个位置
def move_zeros(state, from_pos, to_pos):
    ...

# 辅助函数：统计在指定方向上有多少个连续的0需要移动
def count_zeros_in_direction(state, start_pos, direction):
    ...