你好，同学。今天我们来探讨矩阵运算中最基础也最核心的操作——矩阵转置。

在 NOI 竞赛中，矩阵类题目是考察数组下标处理能力的敲门砖。矩阵转置虽然逻辑简单，但它是后续学习矩阵乘法、图的邻接矩阵转换以及图像处理算法的基础。请跟着我的思路，我们一起在草稿纸上把这个概念解构清楚。

一、 预备知识点

1. 二维数组的定义与存储：理解 matrix[i][j] 中 i 代表行，j 代表列。
2. 矩阵维度的动态变化：理解转置后行数和列数会发生对调。
3. 嵌套循环遍历：掌握如何通过双重循环访问二维结构。

二、 题目描述 (NOI 竞赛风格)

题目名称：转置矩阵 (Transpose Matrix)

【问题描述】 给定一个 $m$ 行 $n$ 列的整数矩阵 $A$。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

具体来说，如果原矩阵 $A$ 的转置矩阵为 $B$，那么对于任意合法的下标 $(i, j)$，都有 $B[j][i] = A[i][j]$。 请你输出该矩阵转置后的结果。

【输入格式】 第一行包含两个正整数 $m$ 和 $n$，表示原矩阵的行数和列数。 接下来 $m$ 行，每行包含 $n$ 个以空格分隔的整数，表示矩阵 $A$ 的元素。

【输出格式】 输出 $n$ 行，每行包含 $m$ 个整数，表示转置后的矩阵 $B$。

【样例 1 输入】

3 3
1 2 3
4 5 6
7 8 9

【样例 1 输出】

1 4 7
2 5 8
3 6 9

【样例 2 输入】

2 3
1 2 3
4 5 6

【样例 2 输出】

1 4
2 5
3 6

【数据规模与约定】

• $1 \le m, n \le 1000$
• $1 \le m \times n \le 10^5$
• $-10^9 \le A[i][j] \le 10^9$

三、 启发式引导：草稿纸上的推理过程

现在，请拿出草稿纸，我们画一个非方阵（比如 $2 \times 3$）来观察：

第一步：建立坐标映射图

我们在纸上写下 $2 \times 3$ 矩阵的每个位置及其坐标：

行0: (0,0)=a  (0,1)=b  (0,2)=c
行1: (1,0)=d  (1,1)=e  (1,2)=f

思考： 转置的定义是“交换行和列的索引”。

• 元素 b 的坐标是 (0, 1)，转置后它的新坐标应该是 (1, 0)。
• 元素 d 的坐标是 (1, 0)，转置后它的新坐标应该是 (0, 1)。

第二步：推导维度的变化

画出转置后的形态：

行0: (0,0)=a  (0,1)=d
行1: (1,0)=b  (1,1)=e
行2: (2,0)=c  (2,1)=f

观察结论： 原矩阵是 $2 \times 3$（2行3列），转置后变成了 $3 \times 2$（3行2列）。 在程序设计中，这意味着你的输出循环边界要从 m 行 n 列 变为 n 行 m 列。

第三步：时间与空间复杂度思考

• 时间复杂度：我们需要访问矩阵中的每一个元素一次。由于总元素个数为 $m \times n$，时间复杂度为 $O(m \times n)$。
• 空间复杂度：
  • 在竞赛中，如果 $m \times n$ 达到 $10^5$，我们可以开一个足够大的二维数组（如 A[1005][1005]）。
  • 空间复杂度为 $O(m \times n)$，用于存储原矩阵或结果矩阵。
• 优化建议：对于转置操作，时间复杂度已是理论最优。在处理超大规模数据时，注意内层循环的访问顺序尽量符合数组在内存中的存储顺序（先横后纵），以提高 CPU 缓存命中率。

四、 NOI 风格 C++14 伪代码提示

// 引入标准库 (iostream)
使用命名空间 标准库;

// 根据数据范围定义常量，注意行列的最大值
常量整型 最大规模 = 1005;
整型 原矩阵[最大规模][最大规模];
整型 结果矩阵[最大规模][最大规模];

函数 解决() {
    整型 m, n;
    读取 m, n;

    // 第一步：读取原矩阵
    对于 i 从 0 到 m-1:
        对于 j 从 0 到 n-1:
            读取 原矩阵[i][j];

    // 第二步：执行转置逻辑
    // 思考：结果矩阵的行数应该是原矩阵的列数 n
    对于 i 从 0 到 m-1:
        对于 j 从 0 到 n-1:
            结果矩阵[j][i] = 原矩阵[i][j];

    // 第三步：输出结果矩阵
    // 易错点：这里的行循环上限是 n，列循环上限是 m
    对于 i 从 0 到 n-1:
        对于 j 从 0 到 m-1:
            输出 结果矩阵[i][j] 以及 空格;
        输出 换行;
}

五、 总结：读题关键词与题型识别

在 NOI 考试中，遇到矩阵题目请迅速定位以下关键词：

1. “主对角线翻转” (Flip over main diagonal)：这是转置的标准定义，核心操作是 swap(i, j)。
2. “行变列” (Rows become columns)：提醒你输出时循环变量的边界（$m$ 和 $n$）必须交换。
3. “非方阵” ($m \neq n$)：如果 $m=n$，转置可以在原数组内通过 swap 完成；如果 $m \neq n$，必须开辟新空间或考虑维度转换，这是最容易写错逻辑的地方。

教练点评： 这道题是典型的**“坐标变换”**类题目。做题时最忌讳直接动笔写代码。先在草稿纸上模拟一个 $2 \times 3 \to 3 \times 2$ 的过程，确认内外层循环的边界到底对应哪个变量，能帮你避开 90% 的低级错误。加油！