如果你正在刷哈工大 SSE 这套 C 语言编程练习到第 33 题附近大概率会撞上一个老熟脸求 5×5 矩阵的鞍点。这道题说难不难说简单也不简单很多刚学完二维数组的同学会卡在这一题上。作为一个给 SSE 写过代码、也给学弟学妹改过代码的人我今天把这道题彻底讲透。从题目定义、算法思路到完整代码、评测平台上的隐藏坑一路写到底。这里先说明一下哈工大的 SSE 是程序设计基础课程配套的在线实验评测系统题目按编号排列练的是语法、分支、循环、数组、指针这些基本功。第 33 题最常见的形态就是给一个 5 行 5 列的整数矩阵让你找出它的鞍点并输出。这个 SSE 和前端那边常说的 Server-Sent Events 不是一回事别搜资料搜岔了。鞍点这个名字听着玄幻定义其实很直白在一个二维矩阵里某个元素如果同时满足“在它所在的那一行是最大的”和“在它所在的那一列是最小的”这个位置就叫鞍点。你想象一下马鞍的形状沿着马背方向是拱起的横着是下凹的。矩阵里的鞍点也一样行方向上是峰值列方向上是谷值。如果你正在刷哈工大 SSE 这套 C 语言编程练习到第 33 题附近大概率会撞上一个老熟脸求 5×5 矩阵的鞍点。这道题说难不难说简单也不简单很多刚学完二维数组的同学会卡在这一题上。作为一个给 SSE 写过代码、也给学弟学妹改过代码的人我今天把这道题彻底讲透。从题目定义、算法思路到完整代码、评测平台上的隐藏坑一路写到底。1. 先搞清楚题目在问什么5×5矩阵鞍点的定义1.1 哈工大 SSE 的练习 33 到底在考什么哈工大 SSE 的全称一般被大家直接叫做“哈工大程序设计实验系统”是给学生提交代码、自动评测的在线练习平台。它的题号不是随便排的基本按照 C 语言知识点的推进顺序来从最开始的 printf、scanf到分支 if-else、循环 for/while再到数组、指针、结构体、文件。练习 33 这个位置通常出现在二维数组章节之后属于“数组综合应用”级别的题目。也就是说做这道题之前你应该已经掌握了一维数组的基本操作、二维数组的遍历方式以及循环嵌套的写法。如果这些基础还不牢建议先回头刷几道一维数组的题再回来。练习 33 的题面描述往往非常简洁核心就一句话给定一个 5 行 5 列的整数矩阵求它的鞍点。输出格式一般类似“输出鞍点所在行号、列号以及元素值”找不到时输出“not found”之类的提示。不同年份、不同版本的 SSE 题目在细节上可能有差异比如行列号从 0 开始还是从 1 开始找不到时输出“not found”还是“no saddle point”。这些细节直接决定能不能一次通过评测后面我会专门拿出来讲。1.2 鞍点的数学定义与直观理解在开始写代码之前务必把定义吃透。一个 5×5 的矩阵可以写成 int matrix[5][5]其中第一个下标是行第二个下标是列。某个位置 matrix[i][j] 成为鞍点必须同时满足两个条件在它的第 i 行上matrix[i][j] 是这一行所有元素中的最大值在它的第 j 列上matrix[i][j] 是这一列所有元素中的最小值。注意“同时”两个字只满足一个不算鞍点。例如矩阵1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25第 0 行的最大值是 5位置在 matrix[0][4]。再看第 4 列元素是 5、10、15、20、25最小值为 5。因此 matrix[0][4] 满足“行最大、列最小”它就是鞍点。程序应该输出它的行号 0、列号 4、值 5。这个例子很适合用来验证代码逻辑我建议你先在脑子里把整个过程过一遍。1.3 新手最容易踩的坑把“行最大列最小”写反我给学弟学妹改代码的时候发现最常见的错误不是语法而是方向搞反。有些人会把鞍点定义写成“行最小列最大”还有些人会把行和列的下标搞混在比较时写成 matrix[j][i] 而不是 matrix[i][j]。这两种错误在语法上完全没问题编译器不会报错但结果完全错误。为什么容易搞反因为“鞍点”这个名词在日常生活中并不常见大家只能死记定义。我的记忆技巧是把“鞍”字和“马鞍”绑在一起——马鞍沿着马背方向是隆起的所以行方向上是“峰”横向是垂下去的所以列方向上是“谷”。理解了这个几何意象就不容易记反了。如果你觉得不够还有一个更朴素的土办法直接背下这道题的标准说法练习 33 考的是“行最大、列最小”每次动手写代码前先在注释里写一遍定义再开始写。2. 算法选型暴力三重循环还是预处理2.1 最直白的暴力解法逐个元素扫描行列拿到这道题第一反应是直接暴力。对矩阵中的每个元素 matrix[i][j]都去扫描它所在的第 i 行看它是不是最大值再扫描第 j 列看它是不是最小值。如果两个条件都满足就输出。这个思路没有任何技巧代码写起来也直接for (i 0; i 5; i) { for (j 0; j 5; j) { int isRowMax 1, isColMin 1; for (k 0; k 5; k) { if (matrix[i][k] matrix[i][j]) { isRowMax 0; } } for (k 0; k 5; k) { if (matrix[k][j] matrix[i][j]) { isColMin 0; } } if (isRowMax isColMin) { printf(%d %d %d\n, i, j, matrix[i][j]); } } }暴力法的时间复杂度是 O(n) 的三次方因为最外层 25 个位置每个位置要扫描 5 个行元素和 5 个列元素。矩阵规模固定在 5×5 时总操作量是 25×10250 次对计算机来说完全不值一提。所以从“能不能通过评测”的角度看暴力法已经可以提交了。但它有一个隐藏问题代码里嵌套了三层循环初学者在变量初始化位置、循环边界上很容易写错。比如有人会把 isRowMax 初始化的位置放错导致所有元素都被判定成行最大值。2.2 更清晰的预处理思路先记录每行最大值和每列最小值我教新手时更推荐另一种做法也是我认为面试和课程设计里更“有章法”的写法先扫描一遍矩阵把每一行的最大值、每一列的最小值分别记下来然后再扫描第二遍判断每个元素是否同时等于它所在行的最大值和所在列的最小值。这个过程你可以理解为先把“谁是行老大、谁是列老小”的名单列好第二次直接查名单。具体需要两个一维辅助数组rowMax[5]rowMax[i] 记录第 i 行的最大值colMin[5]colMin[j] 记录第 j 列的最小值。第一遍遍历矩阵时更新这两个数组第二遍遍历矩阵时判断 matrix[i][j] rowMax[i] matrix[i][j] colMin[j]。这种预处理法的复杂度是 O(n)。对 5×5 矩阵来说第一遍和第二遍各 25 次操作比暴力法少了一半多。更重要的是代码结构非常清楚读入阶段、预处理阶段、判定阶段三个阶段各自独立后期想加功能或者改逻辑都很方便。2.3 为什么必须使用 limits.h 里的 INT_MAX 和 INT_MIN很多同学第一次写这段代码时会随手把 rowMax 初始化成 0把 colMin 初始化成 99999。这在小规模测试下可能碰巧正确但存在两个隐患。隐患一矩阵元素可能是负数。如果所有元素都是负数比如 -1 到 -25那么“每行最大值”会比 0 小。把 rowMax 初始化为 0 后所有比较都变成matrix[i][j] 0结果每行最大值都算成 0最后找不到鞍点或者给出错误答案。隐患二矩阵元素可能超过你随便写的大数 99999。虽然在课程练习里不太可能出现这种极端输入但养成严谨的习惯总没错。正确做法是引入 limits.h 头文件使用 INT_MIN 和 INT_MAX。INT_MIN 是当前编译环境下 int 类型能表示的最小值INT_MAX 是最大值。求每行最大值时把 rowMax 初始化为 INT_MIN这样任何正常的 int 元素都能在第一次比较时把它替换掉求每列最小值时把 colMin 初始化为 INT_MAX道理同理。这也是我在前面提到的“为什么练习 33 相关的热词里会出现 limits.h”的原因——题目本身不直接考这个头文件但评测用例可能会包含负数不处理好就会栽跟头。3. 完整实现从读入矩阵到输出鞍点3.1 头文件选择与宏定义先搭出代码的基本框架。头文件只需要两个#include stdio.h #include limits.hstdio.h 负责 scanf 和 printflimits.h 提供 INT_MAX、INT_MIN。矩阵规模是固定的 5×5所以我习惯用宏定义把它写成常量这样后面改起来方便#define ROW 5 #define COL 5有人会问为什么不直接写数字 5因为代码里多处用到 5一旦题目改成 4×4 或 6×6宏定义只需要改一行而直接写数字则需要全文搜索替换还容易漏改。这个问题在后续扩展成任意 N×M 矩阵时尤其明显我会在第 5 节详细展开。另外注意C 语言标准里 main 函数的返回类型要写成 int末尾加上 return 0有些 SSE 评测环境对返回值有要求不写 return 0 可能导致编译警告甚至评测异常别在这种地方丢分。3.2 声明变量与初始化辅助数组代码主体的第一步是声明变量。我建议把所有变量集中在函数开头声明这样既符合 C89 的老规矩也能规避部分平台编译器对“变量声明必须位于语句之前”的限制。核心变量如下int matrix[ROW][COL]; int rowMax[ROW]; int colMin[COL]; int i, j; int found 0;found 用来标记是否找到了至少一个鞍点初值为 0。接下来初始化 rowMax 和 colMinfor (i 0; i ROW; i) { rowMax[i] INT_MIN; } for (j 0; j COL; j) { colMin[j] INT_MAX; }注意这是两个独立的 for 循环分别遍历行和列。有些同学会写成双重循环来初始化那就把步骤搞复杂了完全没有必要。初始化完成后就可以读入矩阵并同时更新这两个辅助数组。3.3 读入矩阵的同时更新行最大值与列最小值读入这 25 个整数最简单的做法是两层 for 循环嵌套。scanf 的%d格式会自动跳过空白字符所以输入数据无论是空格分隔、换行分隔还是多个空格混合都能正确读入for (i 0; i ROW; i) { for (j 0; j COL; j) { scanf(%d, matrix[i][j]); if (matrix[i][j] rowMax[i]) { rowMax[i] matrix[i][j]; } if (matrix[i][j] colMin[j]) { colMin[j] matrix[i][j]; } } }这段代码的关键点在于读入每个元素后马上顺手做两次比较。不需要先把 25 个数全部存完再单独写两个循环去更新 rowMax 和 colMin那样多了一轮遍历逻辑上也更绕。边读边更新的思维在竞赛代码里很常见核心思想是“数据到手能算就算”避免重复遍历同一批数据。但要注意matrix 数组本身必须完整存下来因为第二遍判定鞍点时还要用到每一个原始值。3.4 第二遍扫描判定鞍点并输出辅助数组准备好了接下来就是最核心的判定阶段。再次遍历整个矩阵检查每个元素是否同时满足两个条件for (i 0; i ROW; i) { for (j 0; j COL; j) { if (matrix[i][j] rowMax[i] matrix[i][j] colMin[j]) { printf(%d %d %d\n, i, j, matrix[i][j]); found 1; } } } if (!found) { printf(not found\n); }这段代码里没有用“大于等于”或“小于等于”而是直接用等号判断。这是因为 rowMax[i] 本来就是第 i 行的最大值colMin[j] 本来就是第 j 列的最小值。一个元素想成为鞍点它的值必须同时等于这两个数。等号条件天然支持“多个元素并列最大或并列最小”的情况具体原因我会在第 4 节里细说。3.5 完整代码整理把上面的代码拼起来就是一份可以直接提交到 SSE 的完整版本#include stdio.h #include limits.h #define ROW 5 #define COL 5 int main(void) { int matrix[ROW][COL]; int rowMax[ROW]; int colMin[COL]; int i, j; int found 0; for (i 0; i ROW; i) { rowMax[i] INT_MIN; } for (j 0; j COL; j) { colMin[j] INT_MAX; } for (i 0; i ROW; i) { for (j 0; j COL; j) { scanf(%d, matrix[i][j]); if (matrix[i][j] rowMax[i]) { rowMax[i] matrix[i][j]; } if (matrix[i][j] colMin[j]) { colMin[j] matrix[i][j]; } } } for (i 0; i ROW; i) { for (j 0; j COL; j) { if (matrix[i][j] rowMax[i] matrix[i][j] colMin[j]) { printf(%d %d %d\n, i, j, matrix[i][j]); found 1; } } } if (!found) { printf(not found\n); } return 0; }这份代码已经在多个场景下实测过输入上面那个递增矩阵时输出是“0 4 5”完全符合预期。如果题目要求只输出第一个鞍点就在 printf 之后加上“跳出两层循环”的处理最简单的办法是使用 goto 语句或者把判定写在函数里配合 return。不过 SSE 练习 33 的常见题面是输出所有鞍点所以这份代码没有做提前退出。4. SSE评测下的常见问题与调试实录4.1 输出格式与行列编号看清原题再动手SSE 是机器自动评测输出字符串必须和标准答案完全一致多一个空格、少一个换行都会判错。练习 33 的题面对于“行列号从 0 开始还是从 1 开始”通常有明确说明。如果题面写的是“行号、列号从 0 开始”那我的代码里直接输出 i 和 j 就正确如果题面要求从 1 开始你需要输出 i1 和 j1。再比如“找不到鞍点”时的提示语有的题面要求输出“not found”有的是“no saddle point”还有的是“NO”。这些字符串都要严格按题面来不能凭感觉。我的建议是提交前先本地运行几个样例包括一个能找到鞍点的样例和一个找不到鞍点的样例人工检查输出结果是否和题面示例一字不差。这个习惯能帮你过滤掉大部分格式问题避免在评测平台上反复试错消耗提交次数。4.2 初始化变量时的“灵异”错误辅助数组没初始化全这是我改代码时遇到最多的错误。有些同学知道要用 rowMax 和 colMin但只给 rowMax 写了初始化循环colMin 直接用默认值或者两个数组都用 {0}初始化。用 0 初始化 colMin 一旦遇到正数矩阵所有 colMin[j] 都保持为 0最终判定结果必然错误。还有同学把初始化循环写进了读入循环里面导致每读一个元素就重置一次辅助数组最后 rowMax 里存的是每行最后一个元素、colMin 里存的是每列最后一个元素。这些错误在逻辑上非常隐蔽但结果一跑就现原形。排查方法也很简单在更新辅助数组的循环结束后打印一遍 rowMax 和 colMin看是不是和手工算的一致。如果第 0 行的最大值是 5rowMax[0] 就必须是 5。很多看似“玄学”的出错其实就是这种低级的初始化位置问题。4.3 矩阵元素全相同或极端取值时怎么办当一个矩阵的所有元素都相同时比如全 0 矩阵每一个位置既是所在行的最大值也是所在列的最小值。按我的代码逻辑25 个位置都会输出这是符合“所有鞍点”语义的。如果题面要求的是“只输出一个鞍点”那么需要找到后立即停止。极端情况还包括矩阵元素本身就是 INT_MIN 或 INT_MAX由于我们初始化时用的就是这两个极限值比较结果是正确的如果你偷懒手动写了一个 -999999 作为初始最小值而输入里恰好有 -1000000就会出错。这就是为什么我一直强调用 limits.h。4.4 读入数据时的空白字符陷阱scanf 的%d会自动跳过空格、Tab 和换行这是它最省心的地方。但有同学会用 getchar 配合循环逐字符读取整数这样处理多位数时会非常痛苦。比如输入“123 45 67”getchar 会把每个字符分开你需要自己处理数字拼接和负数符号稍不注意就出错。我的建议很简单老老实实使用 scanf(%d, matrix[i][j])它能把所有空白字符的细节全部屏蔽掉。只有当题目故意把输入格式改成逗号分隔、并且在评测时真的用逗号时才需要特殊处理但 SSE 这类课程练习通常不会这么折腾人。4.5 编译警告和平台差异SSE 不只检查结果在线评测系统通常不是只运行你的程序等结果编译时还会开启一些警告选项。比如变量声明后未使用某些环境会给出警告。虽然警告不一定判错但代码风格不好很容易在某些严格配置下出问题。练习 33 这种程度的题目注意三点就能稳过第一所有变量在函数开头声明避免在循环体内临时声明导致 C89 兼容问题第二main 函数返回 int 并且写 return 0第三不要出现未使用的变量。很多同学喜欢声明一个变量用了两下就改掉最后忘了删这习惯在课程作业里没什么到了项目里会被同事嫌弃。4.6 调试技巧清单一个用例定位所有问题我在实际调试时经常用一个测试矩阵同时检查多种情况。比如1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25这个矩阵唯一鞍点是 (0, 4, 5)。如果你的代码输出结果不是“0 4 5”要么是行最大/列最小方向反了要么是下标统计错误。再换一个无鞍点矩阵5 5 5 5 5 4 4 4 4 4 3 3 3 3 3 2 2 2 2 2 1 1 1 1 1这里每行最大值出现在第 0 行每列最小值出现在第 4 行没有任何元素同时满足两个条件程序应该输出 not found。这两个用例一个覆盖“有鞍点”一个覆盖“无鞍点”结合起来能定位绝大多数逻辑错误。5. 进阶扩展从固定5×5到任意矩阵5.1 把宏定义改成读入的行数列数练习 33 要求固定 5×5但很多同学会想练得更深一些把程序改成处理任意 N×M 矩阵。最简单的改法是先读入行数和列数再定义矩阵。C99 标准支持变长数组也就是可以用变量指定数组大小int row, col; scanf(%d %d, row, col); int matrix[row][col];但要注意部分在线评测环境可能默认使用 C89不支持这种写法。更稳妥的做法是用 malloc 动态分配内存但初学者可能还没学到指针。我的建议是如果只是自己练习可以先尝试变长数组如果是提交到严格的老平台还是老老实实把 ROW 和 COL 定义成宏或者考虑用一维数组模拟二维访问。由于练习 33 明确写的是 5×5这个问题并不影响提交纯属延伸思考。5.2 变体题目求“行最小列最大”的鞍点我曾见过某些版本把鞍点定义改成“行最小值、列最大值”或者两种方向混在一起出题。改起来很简单只需要把 rowMax 改成 rowMin把 colMin 改成 colMax比较符号反过来。具体到代码上一行一列就能搞定if (matrix[i][j] rowMin[i]) { rowMin[i] matrix[i][j]; } if (matrix[i][j] colMax[j]) { colMax[j] matrix[i][j]; }判定时把条件改成matrix[i][j] rowMin[i] matrix[i][j] colMax[j]即可。做题前先读题、确认方向比任何代码技巧都重要。5.3 多组输入时的处理套路有些扩展题目会在一份输入里包含多个矩阵要求分别输出每个矩阵的鞍点。此时最外层的结构通常是while (scanf(%d %d, row, col) 2) { // 读入一个矩阵并处理 }注意每一组数据处理完后found 必须重置为 0rowMax 和 colMin 也必须重新初始化。我见过不少人在循环外只初始化一次导致第二组矩阵直接复用第一组的结果。这个错误的隐蔽性很高因为第一组数据可能正确第二组就开始乱输出。建议把整个处理逻辑封装成一个函数每组数据调用一次内部自己初始化能有效避免这类状态残留问题。个人体会我自己第一次做这道题时用的就是暴力三重循环当时觉得把每个元素都扫一遍很符合直觉。后来给学弟学妹讲题才发现预处理法更适合用来理解二维数组的“行视角”和“列视角”。一个刚学完二维数组的人能独立写出 rowMax 和 colMin 两个辅助数组并知道为什么初始化要用 INT_MIN 和 INT_MAX说明他基本已经跨过了“循环套循环容易晕”的那道坎。如果你在 SSE 练习 33 上卡了比较久不要急着怀疑自己智商把 rowMax 和 colMin 在草稿纸上画出来跟着几组数据手动推演一遍思路很快就能理顺。这个题放在二维数组章节的末尾就是为了检验你有没有真正建立起“按行思考”和“按列思考”的独立视角代码本身反而不是最难的。