从古风排版到蛇形填充解锁矩阵遍历的通用思维框架当你第一次看到PTA古风排版题时可能会被它独特的输出格式所迷惑——为什么文字要从右往左、从上往下排列这种看似特殊的排版方式实际上揭示了一类更广泛的编程问题二维矩阵的特定路径填充。理解这一点你就掌握了解决蛇形矩阵、螺旋矩阵、Z字形打印等问题的万能钥匙。1. 重新定义问题古风排版的矩阵本质古风排版要求将字符串按列填充到矩阵中但与常规的从左到右填充不同它有两个关键特征列填充顺序从最后一列开始向前填充从右到左行填充方向在每列内部从上往下填充字符这种填充方式可以抽象为一个更通用的模型按照特定路径遍历二维矩阵并填充数据。让我们用一个3行示例拆解这个过程输入字符串This is a test caseN3每列3个字符填充路径如下列序: 2 1 0 (从右到左) 行序: 0→1→2 (每列从上到下)填充后的矩阵行0: T h i 行1: s i s 行2: a t e打印时按行输出就得到了古风效果。这种思维方式让我们看到古风排版只是矩阵填充的一种特殊形式。2. 坐标变换框架统一各类填充问题的解法所有矩阵填充问题的核心都在于控制行列索引的变化规律。我们可以建立一个通用框架def matrix_fill(text, rows, fill_pattern): # 计算需要的列数 cols (len(text) rows - 1) // rows matrix [[None for _ in range(cols)] for _ in range(rows)] # 根据填充模式确定索引变化规则 row, col 0, 0 for char in text: matrix[row][col] char row, col fill_pattern(row, col, rows, cols) return matrix不同的填充模式只需实现不同的fill_pattern函数问题类型列变化规律行变化规律边界处理古风排版从右到左(col--)每列内从上到下(row)列减到0后换列行重置为0蛇形矩阵到达边界后换列(col)奇数列从上到下(row)偶数列从下到上(row--)行越界时改变方向螺旋矩阵按层循环(右→下→左→上)同上检测已访问标记Z字形打印常规顺序(col)斜向交替(row±1,col±1)到达边界时改变斜向这个框架的价值在于只需修改索引变化规则就能解决各类变种问题。例如实现古风排版的fill_patterndef ancient_fill(row, col, rows, cols): row 1 if row rows: # 到达列底部 row 0 col - 1 # 移到左边一列 return row, col3. 从特殊到一般四种经典填充模式的对比理解古风排版后我们可以将其与其他常见填充模式进行对比发现它们本质上的相似性。3.1 蛇形矩阵填充蛇形矩阵的特点是行方向交替变化如1 → 2 → 3 ↓ 6 ← 5 ← 4 ↓ 7 → 8 → 9其填充模式可以表示为def zigzag_fill(row, col, rows, cols): if col % 2 0: # 偶数列向下 row 1 if row rows: row rows - 1 col 1 else: # 奇数列向上 row - 1 if row 0: row 0 col 1 return row, col3.2 螺旋矩阵填充螺旋填充从外向内环绕需要维护方向状态def spiral_fill(row, col, rows, cols, direction): # 方向0右,1下,2左,3上 next_row, next_col row, col if direction 0: next_col 1 elif direction 1: next_row 1 elif direction 2: next_col - 1 else: next_row - 1 if (not 0 next_row rows or not 0 next_col cols or matrix[next_row][next_col] is not None): # 改变方向 direction (direction 1) % 4 return *spiral_fill(row, col, rows, cols, direction), direction return next_row, next_col, direction3.3 Z字形对角线填充Z字形打印沿对角线交替方向1 → 2 6 → 7 ↘ ↙ ↘ 3 5 8 ↑ ↘ ↙ 4 9实现要点def z_fill(row, col, rows, cols, going_down): if going_down: row 1 col - 1 else: row - 1 col 1 # 处理边界 if row 0 or row rows or col 0 or col cols: going_down not going_down if row 0 and col cols: row 0 elif col 0 and row rows: col 0 else: row 2 col - 1 return row, col, going_down4. 实战应用解决PTA L1-039的三种实现方式让我们回到最初的古风排版问题用不同的思维方式实现它体会抽象框架的威力。4.1 基础实现直接模拟填充过程#include stdio.h #include string.h void ancient_print(const char* text, int rows) { int len strlen(text); int cols (len rows - 1) / rows; char matrix[rows][cols]; // 从右到左、从上到下填充 int index 0; for (int c cols - 1; c 0; c--) { for (int r 0; r rows; r) { matrix[r][c] index len ? text[index] : ; } } // 逐行打印 for (int r 0; r rows; r) { for (int c 0; c cols; c) { putchar(matrix[r][c]); } putchar(\n); } }4.2 通用框架实现使用填充模式函数def ancient_fill(row, col, rows, cols): row 1 if row rows: row 0 col - 1 return row, col def matrix_print(text, rows, fill_func): cols (len(text) rows - 1) // rows matrix [[ for _ in range(cols)] for _ in range(rows)] row, col 0, cols - 1 # 从右上角开始 for ch in text: matrix[row][col] ch row, col fill_func(row, col, rows, cols) for r in range(rows): print(.join(matrix[r]))4.3 数学映射法通过计算确定字符位置对于不想使用二维数组的情况可以直接计算每个输出位置对应的原字符串索引def ancient_print(text, rows): length len(text) cols (length rows - 1) // rows for r in range(rows): for c in range(cols): original_pos (cols - 1 - c) * rows r print(text[original_pos] if original_pos length else , end) print()这三种实现展示了从具体到抽象的思维过程。基础实现适合快速解决问题框架实现具有高度可扩展性数学映射则提供了空间优化的思路。5. 举一反三识别和解决变种问题掌握了核心框架后我们可以轻松应对各种变种题目。以下是几个典型例子5.1 旋转90度打印将矩阵旋转90度后按行输出实际是列反向行正向的填充模式def rotate_fill(row, col, rows, cols): col 1 if col cols: col 0 row 1 return row, col5.2 波浪形打印要求输出如波浪般起伏的效果即行索引按0→1→2→1→0→1→2...循环def wave_fill(row, col, rows, cols): if col % 2 0: # 向下移动 row 1 if row rows: row rows - 1 col 1 else: # 向上移动 row - 1 if row 0: row 0 col 1 return row, col5.3 对角线交替打印类似Z字形但沿对角线方向def diagonal_fill(row, col, rows, cols, going_up): if going_up: row - 1 col 1 else: row 1 col - 1 # 边界处理 if row 0 or col 0 or row rows or col cols: going_up not going_up if row 0 and col cols: row 0 elif col 0 and row rows: col 0 else: row 2 col - 1 return row, col, going_up遇到新问题时只需分析其填充路径特征然后实现相应的索引变化逻辑即可。这种思维模式远比记忆特定问题的解法更有价值。