1. 先说清楚这是道什么题为什么值得写1.1 SSE练习34到底在考什么在哈工大软件学院的SSEStudent Software Environment在线练习平台上C语言课程练到二维数组这一章基本都会碰到这道鞍点问题。题号是34但很多同学其实不是卡在“不会写二维数组”而是卡在“鞍点到底是什么”和“输出格式怎么跟评测程序对齐”这两件事上。刷过几个OJ平台的人可能都有同感代码逻辑明明对本地跑样例也全通过一传到评测系统就是Wrong Answer最后发现是下标从0开始还是从1开始的问题。这道题就是这种“细节决定成败”的典型代表。SSE平台本质上是一个自动评测系统你提交的代码会被编译运行然后用预设的测试数据去对比你程序的输出。它不看过程只看结果。所以很多在学校里写惯了“能跑就行”代码的同学第一次在SSE上做题会特别不适应。练习34作为二维数组章节里的压轴题之一恰好把数组遍历、极值查找、条件筛选、格式化输出这些基础能力串在一起算是C语言学习路上一次很实在的综合体检。1.2 鞍点这个概念怎么理解先别被“鞍点”这个词吓到。它来自数学里的一个概念放到二维矩阵里定义其实很朴素一个位置上的数要求它在自己那一行里是最大的同时在自己那一列里是最小的这个位置就叫鞍点。举个例子一个5行5列的矩阵假如第3行第2列的元素是8它比第3行其他4个数都大同时又比第2列其他4个数都小那这个位置就是鞍点。你可以这样想象在行方向上是“山尖”在列方向上是“谷底”整张矩阵就像一张马鞍鞍点正好是那个交互的位置这也是“鞍点”名称的由来。这个定义里有一个特别容易被忽视的关键点行最大、列最小这两个条件必须同时成立缺一不可。很多同学写代码的时候只找行最大值找到以后直接输出完全没验证它在列上是不是最小这种代码碰巧能过几个简单的测试点但只要矩阵设计得稍微复杂一点马上就会漏判或误判。这篇博客我会把这类问题全部拆开讲清楚。2. 动手之前先建模输入、输出、边界条件2.1 题目的一般输入输出格式SSE练习34的题目描述大同小异通常是这样输入一个5×5的整数矩阵共25个整数一般按5行排列输入每行5个数数与数之间用空格或换行分隔。输出如果矩阵中存在鞍点则输出它的行下标、列下标和值格式一般是“行下标 列下标 值”中间用空格隔开如果不存在鞍点则输出“not found”。我见过有的同学在本地测试的时候习惯性地加上“请输入矩阵”之类的提示语句这在SSE平台上就是致命错误。评测程序是拿你程序的输出和标准答案做逐字符比对的多一个空格、多一个换行都可能被判错更别说多一行提示文字了。这种输出格式敏感的问题在OJ上第一次吃亏几乎是所有人的必经之路。2.2 最容易忽略的两个边界条件第一个边界条件是“并列极值”。按照鞍点的定义它只要求“行内最大”和“列内最小”没有说必须是唯一最大或唯一最小。所以如果某一行里有两个并列的最大值这两个位置都有可能是鞍点需要逐一检查。举个例子矩阵某一行是“6 3 6 2 1”那么这一行的两个“6”都满足行内最大。如果第0列的列最小值恰好也是6那就需要把(行, 0)这个位置输出如果第2列的列最小值也是6那(行, 2)也要输出。很多新手只记录了行最大值的第一个出现位置用一个int rowPos变量保存结果遇到并列情况就只能找到一个直接漏判。第二个边界条件是“矩阵中是否存在负数”。如果题目不保证所有数字都是正数那么找行最大值时初始值就不应该用0。设想矩阵第一行全是负数比如“-5 -3 -8 -2 -9”如果你把行最大值初始化为0那整个扫描过程里maxVal永远不会被更新最后输出行最大值就是0完全错误。正确做法是使用limits.h里的INT_MIN作为初始值因为INT_MIN是int类型能表示的最小值用它做比较基准第一次比较必然会被替换成实际元素值。3. 两种解法暴力三重循环和预处理数组3.1 思路一逐行逐列硬刚n很小够用最直观的思路是对每一个位置(i, j)先去它的行里确认是不是最大再去它的列里确认是不是最小。写成伪代码就是下面这样for (i 0; i 5; i) { for (j 0; j 5; j) { // 判断 a[i][j] 是否是第 i 行的最大值 int isRowMax 1; for (k 0; k 5; k) { if (a[i][k] a[i][j]) { isRowMax 0; break; } } // 判断 a[i][j] 是否是第 j 列的最小值 if (isRowMax) { int isColMin 1; for (k 0; k 5; k) { if (a[k][j] a[i][j]) { isColMin 0; break; } } if (isColMin) printf(%d %d %d\n, i, j, a[i][j]); } } }这个写法时间复杂度是O(n^3)因为最外层有两层循环中间还有一层n次的扫描。对n5的矩阵来说最多就是125次比较运行时间完全可以忽略不计。优点是代码简单直接不容易想错缺点是我们为了判断每一个位置反复扫描了很多遍同一行同一列做了大量重复工作。如果哪天题目把矩阵改成500×500这个写法就不太行了。3.2 思路二预处理行最大值和列最小值推荐更推荐的做法是预处理。先用两个长度为5的数组把所有行的最大值和所有列的最小值一次性算好存储起来然后再用两层循环去比对。这样只需要O(n^2)的时间而且代码结构还更清晰。具体来说定义两个数组int rowMax[5]; int colMin[5];第一遍扫描矩阵填充这两个数组for (i 0; i 5; i) { rowMax[i] INT_MIN; colMin[i] INT_MAX; } for (i 0; i 5; i) { for (j 0; j 5; j) { if (a[i][j] rowMax[i]) rowMax[i] a[i][j]; if (a[i][j] colMin[j]) colMin[j] a[i][j]; } }第二遍扫描矩阵判断每个位置是否同时满足两个条件for (i 0; i 5; i) { for (j 0; j 5; j) { if (a[i][j] rowMax[i] a[i][j] colMin[j]) { printf(%d %d %d\n, i, j, a[i][j]); } } }这个思路的精妙之处在于它把“行内比较”和“列内比较”提前到预处理阶段完成判断阶段只剩常数时间的比较操作。在n很小的时候可能感觉不到差异但这种“空间换时间”的预处理思想后面学算法的时候会频繁用到比如前缀和、哈希表预统计本质都是类似思路。而且用这个写法并列极值的处理变得很自然因为rowMax[i]保存的是一个数值只要a[i][j]等于这个值就说明它是行内最大之一不需要关心它是不是唯一的那个。3.3 为什么要求用limits.h不是刁难你有些老师给这道题明确附加了要求必须包含stdio.h和limits.h。有的同学不理解觉得limits.h有什么好用的直接#define INF 99999不就行了。这种想法在初学者阶段很常见但认真说起来用宏定义一个“足够大的数”来充当哨兵是有隐患的。你定义INF为99999是因为你默认矩阵里的数不会超过99999。可题目从来没这么保证过。如果某次测试数据里出现了100000你的INF就失效了行最大值初始值比所有数都大扫描结束之后maxVal还是100000错误悄无声息地就产生了。INT_MIN和INT_MAX是C语言标准规定的int类型边界值任何int值都不可能小于INT_MIN或大于INT_MAX用在初始化场景下天然安全。它是语言本身给出的常量不需要你猜测数据范围这就是专业工程里“用标准不猜数据”的思路。这也是我在实际写代码时一直养成的习惯找最大值就初始化为INT_MIN找最小值就初始化为INT_MAX而不是自己拍脑袋定义一个“很大”的数。你永远猜不到测试数据会干什么。4. 完整代码与逐段解读4.1 一份可以直接提交的代码把上面的思想整合到一起给出完整代码。这段代码针对5×5矩阵两个空格和一个换行的输出格式都可以根据题目要求微调但整体结构可以直接用于SSE提交#include stdio.h #include limits.h #define N 5 int main() { int a[N][N]; int rowMax[N], colMin[N]; int i, j; int found 0; // 读入5x5矩阵 for (i 0; i N; i) for (j 0; j N; j) scanf(%d, a[i][j]); // 初始化行最大值与列最小值 for (i 0; i N; i) { rowMax[i] INT_MIN; colMin[i] INT_MAX; } // 第一遍扫描统计 for (i 0; i N; i) { for (j 0; j N; j) { if (a[i][j] rowMax[i]) rowMax[i] a[i][j]; if (a[i][j] colMin[j]) colMin[j] a[i][j]; } } // 第二遍扫描判断鞍点 for (i 0; i N; i) { for (j 0; j N; j) { if (a[i][j] rowMax[i] a[i][j] colMin[j]) { printf(%d %d %d\n, i, j, a[i][j]); found 1; } } } if (!found) printf(not found\n); return 0; }这里有一个小细节需要注意题目如果规定“只输出一个鞍点”那么找到第一个之后就应该用break跳出循环或者用goto直接跳到程序结尾。但多数SSE版本的题目没有强调唯一性而是问“是否存在鞍点存在则输出”所以我这里默认输出所有满足条件的鞍点。如果题目要求只输出一个你在判断循环里找到第一个后直接return 0就行。4.2 关键代码段拆解读入部分我用嵌套循环配scanf相信大家都已经非常熟悉了。scanf在处理整数时会自动跳过换行符和空格所以输入排列是5行还是1行递过来25个数对这个代码没区别这一点在很多图形化界面的练习环境里表现得尤其明显你从控制台粘贴数据的时候不用刻意对齐行列。预处理阶段有两个细节值得说。第一个是我用宏N来表示矩阵大小而不是在代码里硬编码5。将来题目变成10×10或者其他尺寸只需要改宏定义那一行。第二个是rowMax和colMin数组的初始化方式。我在同一层循环里同时初始化两个数组有人可能会问rowMax[i]用INT_MINcolMin[i]用INT_MAX一个找最大一个找最小对比基准方向完全相反为什么要放在一起初始化其实只是代码编排上的方便你也可以分开两个循环效果完全一样。判断阶段是整个代码的核心。我直接比较a[i][j]是否同时等于rowMax[i]和colMin[j]这个写法比“先记录一个位置再回头去验证”要优雅得多。它不关心这个行的最大值出现在几个位置、列的最小值出现在几个位置只要当前这个点既是行最大又是列最小它就是一个鞍点。如果你用了“记录位置再验证”的方式通常会这样写先找出行最大元素的第一个位置然后把列扫描一遍确认它是最小值。这种写法遇到并列极值时只能处理第一个位置遇到一个矩阵里多个鞍点并存的情况更是完全无能为力所以我不推荐。found变量是用来记录“是否至少找到了一个鞍点”。有些同学会写一个计数器找到鞍点就count最后if (count 0)输出not found效果一样但用布尔性质的found标志更直观。这个变量在整段代码里的作用很单纯判断完所有位置之后如果一次都没置位就说明矩阵里不存在鞍点。我建议把返回类型int和return 0写上。SSE平台评测时主要看标准输出但养成C语言规范习惯很重要很多后续课程和面试笔试都会检查代码规范不要因为题目简单就随手写void main。5. 我踩过的坑常见错误与排查实录5.1 这类题最冤的扣分点第一坑下标从1开始输出。矩阵在C语言里天然是从0开始索引的但有些教材喜欢从1开始描述行列。SSE练习34的题目描述里如果示例输出是“1 1 7”这种说明它要求从1开始输出行号和列号那你需要在printf里对i和j都加1。很多同学挂在这里代码逻辑完全正确但输出“0 0 7”和标准答案“1 1 7”不一致直接Wrong Answer。破解办法是看样例输出样例就是标准答案照着它写格式。第二坑忽略了“not found”的拼写和大小写。有的题目要求输出“No saddle point”有的要求“not found”有的要求“None”大小写也可能不同。这些细节在本地测试时不会报错但评测系统比对字符串时任何一个字符不对都是错。我建议提交前用记事本把标准样例原原本本跑一遍输出能跟样例逐字符一致再提交。第三坑并行极值漏判。前面反复提到的那一点如果你用单个位置变量记录行最大值遇到并列情况就凉了。SSE的测试数据常常会专门构造这种边界数据否则题目就太没区分度。比如下面这个矩阵1 2 3 4 5 2 1 4 3 2 1 2 3 4 3 5 4 3 2 1 2 3 1 4 5第2行下标从0开始有多个3和多个4如果不逐个比较所有位置就很容易漏掉真正的鞍点。使用预处理数组方案之后这个隐患从根上被消除了。第四坑初始化用0找最大值。这个坑在前面已经详细说过矩阵里出现负数时0作为初始值就会导致误判。有同学可能会说“题目保证了矩阵元素范围”但很多题目没写这句话。稳妥处理就是使用INT_MIN和INT_MAX。第五坑忘记include头文件。有的同学在本地IDE里写代码IDE自动补全了stdio.h提交到SSE上却因为某些配置问题只贴了核心代码结果编译报错。我在给新手答疑时遇到好几次这种问题代码里用了INT_MIN却忘了写#include limits.h。这属于低级失误但确实会让人在评测页面上反复琢磨好几分钟。5.2 调试和排查建议本地调试时除了题目给的样例我强烈建议你额外构造几组测试数据全正数矩阵包含唯一鞍点验证基本逻辑。包含负数矩阵验证INT_MIN、INT_MAX初始化的正确性。行或列存在并列极值验证多鞍点场景。严格递增的矩阵例如对角线元素特别大这种矩阵通常不存在鞍点验证not found路径。矩阵元素全部相同比如25个5那每个位置都满足行最大且列最小应当输出25个结果这类极端的全等矩阵能测出你输出逻辑里是否有重复或遗漏。调试时如果发现“本地对提交错”先检查输出格式、下标偏移、头文件和终止条件。这三类问题占了OJ错误的大部分比例算法本身反而很少出问题。6. 这题背后的通用套路以后还能用在哪6.1 “候选验证”的筛选思想鞍点问题的核心套路可以总结成八个字先提候选再验条件。把行最大值先筛出来作为候选再对这些候选做列最小验证。这个模式在很多场景里都极其常见。比如学生信息管理先筛选“成绩大于90的所有学生”作为候选列表再从中找出“课外实践学分也满足条件”的学生这种多条件筛选逻辑在数据库查询和日常编程里到处都是。再比如字符串处理中先筛选出符合某种模式的所有位置再验证前后缀条件。如果你能把鞍点问题吃透实际上你就掌握了“用空间记录中间结果、分阶段筛选”的核心编程思维这比单纯会写一个二维数组实用得多。6.2 变体题与扩展思路很多高校的C语言练习平台其实都有这道题的变体只是矩阵大小和输出语言略有不同。比如有的要求输入一个任意行列的矩阵用m和n表示行列数有的要求输出所有鞍点坐标有的只要输出鞍点个数还有的题目会把定义反过来行最小、列最大也称鞍点。刷题时不用每道题都从零开始只要核心逻辑想通改起来就是改几个比较方向的事。我个人还喜欢做一步额外的思维训练如果矩阵扩大到1000×1000预处理数组方案依然是O(n^2)完全跑得动但如果继续扩大到1万×1万内存占用就会成为新的瓶颈这时候就要考虑能不能只读一遍矩阵、不存整个数组而实时判断。这种递进式的思考方式在面试准备阶段特别管用因为面试官经常不会满足于“你写出来了”而是会继续问“如果规模更大你怎么办”。鞍点这道题虽然是小练习但用来推导这类规模扩展问题是非常好的切入点。最后分享一个我写这类题的小习惯变量名尽量用能表达语义的单词比如用rowMax而不是m1用colMin而不是m2用found而不是f。虽然C语言里短变量名没任何问题但在后面调试或回看代码时语义化命名的代码读起来真的轻松非常多。练习34是C语言学习的一座小山丘翻过去不难但翻过去的时候把基础打扎实了后面遇到指针、结构体、链表那些真正的坎才会走得更顺。