Python怎么实现M行N列矩形蛇形矩阵填充

一、矩形蛇形矩阵填充的核心概念与难点

在矩阵填充问题中，所谓的“蛇形矩阵”在算法题目和实际业务里主要包含两种形态：第一种是按顺时针方向自外向内层层绕转的“螺旋回形填充”（LeetCode 54/59 经典模型）；第二种是行与行之间交替正反向折返的“S 形波浪填充”。

当矩阵是正方形（M = N）时，边界对称，顺时针循环往往比较规律。但当矩阵为任意矩形（M ≠ N）时，行数与列数不对等会导致收缩速度不同步。在最内层收缩结束前，极易出现只剩“单行”或“单列”的情况。如果缺乏严格的边界判断，就容易引起重复填充或数组越界。因此，写好非方阵矩形填充的核心，在于精确把握收缩边界的生效时机与终止条件。

图 1：M×N 矩形蛇形矩阵的四向边界定义与收缩示意图

二、方法一：四边界收缩法（推荐首选）

四边界收缩法的思路非常直观：我们将矩阵抽象出四个指针：顶部边界 top、底部边界 bottom、左侧边界 left 和右侧边界 right。

每一轮循环依次执行四次移动：

1. 从左到右填充当前 top 行的所有可用列，填完后将 top 下移一行（top += 1）；
2. 从上到下填充当前 right 列的所有可用行，填完后将 right 左移一列（right -= 1）；
3. 关键判定：检查 top <= bottom 是否仍然成立。若成立，从右到左填充当前 bottom 行，填完后将 bottom 上移一行（bottom -= 1）；
4. 关键判定：检查 left <= right 是否仍然成立。若成立，从下到上填充当前 left 列，填完后将 left 右移一列（left += 1）。

图 2：四边界收缩算法的判定与流转过程

Python 完整代码实现

def generate_spiral_matrix(m: int, n: int) -> list[list[int]]:
    """
    生成 M 行 N 列的顺时针螺旋蛇形矩阵
    :param m: 矩阵行数
    :param n: 矩阵列数
    :return: 填充好的二维列表
    """
    if m <= 0 or n <= 0:
        return []

    # 1. 初始化 M 行 N 列的二维数组，初始值置为 0
    matrix = [[0] * n for _ in range(m)]

    # 2. 初始化上下左右四个边界
    top, bottom = 0, m - 1
    left, right = 0, n - 1

    # 填充计数器
    current_val = 1
    total_elements = m * n

    while top <= bottom and left <= right:
        # 步骤 1：从左向右填充顶行
        for col in range(left, right + 1):
            matrix[top][col] = current_val
            current_val += 1
        top += 1

        # 步骤 2：从上向下填充右列
        for row in range(top, bottom + 1):
            matrix[row][right] = current_val
            current_val += 1
        right -= 1

        # 步骤 3：从右向左填充底行（需确保 top 仍不超过 bottom）
        if top <= bottom:
            for col in range(right, left - 1, -1):
                matrix[bottom][col] = current_val
                current_val += 1
            bottom -= 1

        # 步骤 4：从下向上填充左列（需确保 left 仍不超过 right）
        if left <= right:
            for row in range(bottom, top - 1, -1):
                matrix[row][left] = current_val
                current_val += 1
            left += 1

    return matrix

def print_matrix(mat: list[list[int]]) -> None:
    """格式化对齐打印矩阵"""
    if not mat:
        print("[]")
        return
    # 计算最大数字的位宽以便制表对齐
    max_num = max(max(row) for row in mat)
    width = len(str(max_num))
    for row in mat:
        print(" ".join(f"{num:>{width}}" for num in row))

# 测试 4 行 5 列的矩形矩阵
if __name__ == "__main__":
    m, n = 4, 5
    result = generate_spiral_matrix(m, n)
    print(f"--- {m} 行 {n} 列 矩形螺旋填充结果 ---")
    print_matrix(result)

输出示例：

--- 4 行 5 列 矩形螺旋填充结果 ---
 1  2  3  4  5
14 15 16 17  6
13 20 19 18  7
12 11 10  9  8

三、方法二：方向向量与碰撞转向法

除了显式维护四条收缩边界，还可以采用在游戏或机器人路径规划中常见的“方向向量模拟法”。这种方法将填充动作看作一个小人在网格中前行：

• 小人拥有初始坐标 (row, col) = (0, 0)；
• 预设好顺时针方向的四个行进向量：右 (0, 1)、下 (1, 0)、左 (0, -1)、上 (-1, 0)；
• 每次行进前计算下一步位置 next_row = row + dr, next_col = col + dc；
• 如果下一步超出网格边界，或者目标单元格已经被填过数字（matrix[next_row][next_col] != 0），说明发生了“碰撞”，此时顺时针切换到下一个行进方向；
• 重复这个过程，直到所有 $M \times N$ 个格子全部填满。

图 3：方向向量步进模拟与碰撞转向示意图

Python 完整代码实现

def generate_spiral_by_vectors(m: int, n: int) -> list[list[int]]:
    """
    通过方向向量与碰撞转向生成 M 行 N 列螺旋矩阵
    """
    if m <= 0 or n <= 0:
        return []

    matrix = [[0] * n for _ in range(m)]

    # 顺时针四个方向向量：右、下、左、上
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    dir_idx = 0  # 初始方向：向右

    row, col = 0, 0
    total = m * n

    for val in range(1, total + 1):
        matrix[row][col] = val

        # 尝试走下一步
        dr, dc = directions[dir_idx]
        next_row, next_col = row + dr, col + dc

        # 碰撞检查：若越界或已填过值，则顺时针转 90 度
        if not (0 <= next_row < m and 0 <= next_col < n and matrix[next_row][next_col] == 0):
            dir_idx = (dir_idx + 1) % 4
            dr, dc = directions[dir_idx]
            next_row, next_col = row + dr, col + dc

        row, col = next_row, next_col

    return matrix

四、变体扩展：S 形折返（之字形）蛇形矩阵

除螺旋回旋外，许多场景下“蛇形矩阵”指的是按行交替折返的模式（即第 0 行从左往右填，第 1 行从右往左填，第 2 行再从左往右填……）。这种填充形式在 LED 点阵屏扫描、图像光栅排布中极为常见。

其逻辑无需处理复杂边界，只需根据行号的奇偶性决定行内数值是正向放入还是逆向放入即可：

def generate_zigzag_matrix(m: int, n: int) -> list[list[int]]:
    """
    生成 M 行 N 列交替折返的 S 形蛇形矩阵
    """
    matrix = []
    val = 1
    for r in range(m):
        row = []
        for _ in range(n):
            row.append(val)
            val += 1
        # 奇数行翻转，实现折返效果
        if r % 2 == 1:
            row.reverse()
        matrix.append(row)
    return matrix

# 示例: 3 行 4 列 S 形折返填充
# 1  2  3  4
# 8  7  6  5
# 9 10 11 12

五、两种主流蛇形矩阵实现方案对比

针对 M 行 N 列的矩形网格，不同解法在代码结构与维护成本上各有侧重。下表给出了核心维度的对比总结：

图 4：三种矩形蛇形填充方案定位与选型总结

六、容易踩坑的关键注意事项

掌握以上边界控制要领与推导过程，在遇到任意行数 M 与列数 N 的矩形蛇形填充需求时，都能写出逻辑严密、运行高效的 Python 代码。