第十三天：蛇形矩阵

每日一道C++题：蛇形矩阵

问题：给你一个整数n，输出n∗n的蛇形矩阵。

要求：输入一行，包含一个整数n；输出n行，每行包含n个正整数，通过空格分隔。（1<=n<=1000）

1. 蛇形矩阵的规律：蛇形矩阵的填充方式是按行填充，但奇数行（从 0 开始计数或从 1 开始计数，这里需要注意，不同的计数方式会影响判断逻辑）是从左到右填充，偶数行是从右到左填充（或者相反，根据具体的蛇形定义 ）。更准确地说，对于 n×n 的矩阵，第 i 行（ i 从 0 开始 ），如果 i 是偶数，则从左到右填充数字；如果 i 是奇数，则从右到左填充数字。
2. 矩阵初始化与填充：首先创建一个 n×n 的二维数组（矩阵 ），然后按照蛇形的规律依次填充数字。可以使用一个变量 num 从 1 开始递增，按照行的奇偶性来决定填充方向，将 num 依次赋值给矩阵的对应位置。

#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<vector<int>> matrix(n, vector<int>(n, 0));int num = 1; // 要填充的数字，从 1 开始for (int i = 0; i < n; ++i) {if (i % 2 == 0) {for (int j = 0; j < n; ++j) {matrix[i][j] = num++;}} else {for (int j = n - 1; j >= 0; --j) {matrix[i][j] = num++;}}}for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cout << matrix[i][j];if (j != n - 1) {cout << " ";}}cout << endl;}return 0;
}

• vector<vector> matrix(n, vector(n, 0)); 创建一个 n 行 n 列的二维向量（矩阵 ），并将所有元素初始化为 0 。
• 外层循环 for (int i = 0; i < n; ++i) 遍历矩阵的每一行。
• 对于每一行 i ，判断其是偶数行（ i % 2 == 0 ）还是奇数行（ i % 2 != 0 ）：
• 如果是偶数行，内层循环 for (int j = 0; j < n; ++j) 从左到右遍历该行的列，将 num 的值依次赋给 matrix[i][j] ，然后 num 自增 1 。
• 如果是奇数行，内层循环 for (int j = n - 1; j >= 0; --j) 从右到左遍历该行的列，同样将 num 的值依次赋给 matrix[i][j] ，然后 num 自增 1 。
• 外层循环 for (int i = 0; i < n; ++i) 遍历矩阵的每一行。
• 内层循环 for (int j = 0; j < n; ++j) 遍历该行的每一列，输出 matrix[i][j] 的值，并且在除了该行最后一个元素外，输出一个空格用于分隔元素。每行输出完后，输出一个换行符 endl 。

1. 二维数组的创建与操作

• 动态数组的初始化：
  用 vector<vector> matrix(n, vector(n, 0)) 创建 n×n 矩阵，避免手动管理内存（如 new / delete ），适合题目中 n≤1000 的规模。
• 二维数组的遍历：
  嵌套循环遍历行和列，外层控制行（ i ），内层控制列（ j ），需注意行列的边界条件（ j < n 或 j >= 0 ）。

2. 蛇形填充的逻辑控制

• 方向切换的本质：
  通过判断行号 i 的奇偶性（ i % 2 == 0 或 i % 2 != 0 ），决定列的遍历方向（左→右或右→左 ）。这是条件分支与循环结合的典型应用。
• 数字递增的连续性：
  用 num++ 保证填充的数字从 1 到 n² 连续，核心逻辑是全局计数器的维护（ num 不能局部于内层循环 ）。

3. 输出格式的精确控制

• 分隔符与换行：
  内层循环中，通过 if (j != n-1) cout << " "; 控制空格输出（最后一个元素后不加空格 ）；外层循环末尾用 cout << endl; 换行，严格匹配题目格式要求。

4. 时间与空间复杂度分析

• 时间复杂度：
  填充和输出的总操作数是 O(n²) （遍历整个 n×n 矩阵 ），对于 n=1000 ， 1e6 次操作在题目时间限制（1秒 ）内完全可行。
• 空间复杂度：
  存储矩阵需要 O(n²) 空间， n=1000 时约占 4MB （每个 int 占 4 字节 ），远低于题目空间限制（32MB ）。

5. 蛇形方向的变种（灵活控制填充规则）

• 场景：题目中是“偶数行左→右，奇数行右→左”，但实际可能有其他蛇形规则（如：第一行左→右，第二行右→左，第三行左→右 … 或反向起始 ）。
• 扩展思路：
• 定义方向变量（如 bool isLeftToRight ），每行结束后切换方向（ isLeftToRight = !isLeftToRight ）。

bool isLeftToRight = true;
for (int i = 0; i < n; ++i) {if (isLeftToRight) { /* 左→右填充 */ } else { /* 右→左填充 */ }isLeftToRight = !isLeftToRight; // 切换方向
}

6. 蛇形矩阵的螺旋变种（二维螺旋填充）

• 需求场景：输出螺旋矩阵（从外围到中心顺时针/逆时针填充 ），如

1  2  3  4
12 13 14 5
11 16 15 6
10 9  8  7

• 定义四个边界（上、下、左、右 ），按“右→下→左→上”的顺序循环填充，每完成一圈缩小边界。

int top = 0, bottom = n-1, left = 0, right = n-1;
int num = 1;
while (top <= bottom && left <= right) {// 向右填充for (int j = left; j <= right; ++j) matrix[top][j] = num++;top++;// 向下填充for (int i = top; i <= bottom; ++i) matrix[i][right] = num++;right--;// 向左填充（需判断边界）if (top <= bottom) {for (int j = right; j >= left; --j) matrix[bottom][j] = num++;bottom--;}// 向上填充（需判断边界）if (left <= right) {for (int i = bottom; i >= top; --i) matrix[i][left] = num++;left++;}
}

底层原理与效率本质

1. 二维数组的内存布局

• C++ 中 vector<vector> 的存储：
  外层 vector 存储多个内层 vector 的指针，内层 vector 存储实际的 int 数据。因此，二维数组的物理存储是分散的（不同行可能不在连续内存 ）。
• 缓存友好性：
  蛇形填充的顺序（按行连续访问 ）对缓存更友好（CPU 预读机制可发挥作用 ），而随机访问二维数组会导致缓存失效，降低效率。可尝试用一维数组模拟二维数组（ matrix[i * n + j] ），提升缓存命中率（尤其对大 n ）。

2. 时间复杂度的深层理解

• 填充逻辑的常数优化：
  题目中 O(n²) 的时间复杂度是理论上界，但实际运行时间受循环开销（条件判断、变量自增 ）影响。可通过减少内层循环的条件判断（如预处理方向数组 ）优化：

// 预处理每行的方向（0 表示左→右，1 表示右→左）
vector<int> dir(n, 0);
for (int i = 1; i < n; ++i) dir[i] = 1 - dir[i-1]; 
// 填充时直接判断方向
if (dir[i] == 0) { /* 左→右 */ } else { /* 右→左 */ }