在哈工大SSE的C语言练习列表里第34题不是最难的却是最容易让你怀疑自己“是不是没读懂题意”的一道。题目要求对一个5x5矩阵找出鞍点所谓鞍点就是该位置在其所在行最大、同时在其所在列最小的元素。很多同学第一次做这道题觉得不就是双重循环找最大值吗实际提交却总被判错。原因在于“鞍点”必须同时满足两个条件而且矩阵里可能有多个鞍点也可能一个都没有。我当年在这题上反复提交了七八次踩遍了各种坑所以今天想把这道题的完整解法、常见错误和平台提交经验一次说清楚给正在刷SSE题库的朋友一份可以直接抄作业的参考。1. 题目背景与需求拆解1.1 SSE第34题到底在问什么SSE平台是哈工大本科生C语言课程的配套编程练习系统题号34一般是二维数组章节的中等难度题。题目原文大致可以理解为输入一个5x5的整数矩阵找出其中的鞍点。鞍点的定义是该位置上的数字在其所在行中是最大值并且在其所在列中是最小值。输出时要求给出鞍点的行号、列号和值如果矩阵中不存在鞍点输出一个指定的提示信息。这道题和单纯的“找最大值”“找最小值”最大的区别在于它要求你同时关注行和列两个维度。换句话说你需要把一个元素放到两个不同的上下文里去比较。很多初学者会把“行最大”和“列最小”拆开单独做结果要么找到了行最大但忘了验证列最小要么找到了列最小却忽略了行最大。所以读懂题目的第一步是明确这个“并且”的关系两个条件缺一不可。另外SSE平台版本不同题目描述可能略有差异。有的版本要求输出“第i行第j列”行列从1开始编号有的则从0开始编号。如果你不在编码前先确认行列编号规则后面输出坐标就容易整体偏移一位。我见过不少同学在本地测试时用的是0基坐标提交后却全部WAWrong Answer改一个起始值就通过了。1.2 数学定义与边界条件用数学语言描述鞍点给定矩阵A元素A[i][j]是鞍点当且仅当A[i][j]等于第i行的最大值并且A[i][j]等于第j列的最小值。这里要特别注意“最大值”和“最小值”的范围是整行和整列不是相邻元素也不是某个局部区域。一个典型的陷阱是如果某一行有多个元素都等于该行最大值那么这些元素都有资格参与后续的列最小判断。你不能在找到第一个“行最大”后就break因为那可能不是唯一的候选。同理某一列也可能有多个最小值。所以在判断时必须遍历所有5x5个位置逐一验证每个位置是否同时满足两个条件。边界条件还包括矩阵元素可能是负数。很多新手写代码时喜欢给“最大值”初始化为0然后遍历更新。如果矩阵全是正数这没问题但如果测试数据里包含负数初始值0就会让所有真正的负数最大值被漏掉。更稳妥的做法是拿矩阵的第一个元素作为初始值或者使用limits.h提供的INT_MIN和INT_MAX。题目给出的提示“使用stdio.h和limits.h”其实就是在暗示这一点你需要考虑int类型的上下界而不是想当然地选一个“足够小”或“足够大”的魔法数字。1.3 为什么这道题值得反复刷鞍点问题虽然只有5行5列但它把二维数组、嵌套循环、标志位管理、最值初始化这几个核心考点全部串起来了。在SSE的题库里这道题是后续“矩阵转置”“杨辉三角”“螺旋矩阵”等二维数组题目的基础。如果你能在一开始就养成“先求每行最大值再求每列最小值最后逐点匹配”的思维模式后面做稍微复杂一点的矩阵题会顺畅很多。而且这道题非常适合用来练习调试技巧。因为它逻辑不复杂但错误类型很多数组越界、初始值错误、比较条件写错、坐标输出格式错误……每一个都能让程序行为异常。我当年在这题上反复试错硬是把gdb的基本断点、单步调试、打印变量操作全部摸熟了。现在回头看这道题之于我就是“磨刀石”。2. 解题思路与算法设计2.1 暴力遍历法最直接也最容易出错最朴素的想法是对每个元素A[i][j]先扫描第i行的所有元素判断它是不是最大值再扫描第j列的所有元素判断它是不是最小值。如果两个条件都满足就记录并输出。这种做法的优点是逻辑直观代码写出来很容易读。缺点是时间复杂度是O(n^3)因为需要三重循环外层遍历每个元素内层分别扫描行和列。不过在n5时最多只需要比较5×5×5125次耗时几乎为0所以不是性能问题而是容易写错的问题。具体容易错在哪第一扫描行和扫描列的顺序。有些人喜欢先验证列最小再验证行最大这在逻辑上并没有错但会让人更倾向于使用“提前退出”的写法。比如在一个元素所在列中只要发现有更小的就立刻跳过该元素不再去看行。这个逻辑是对的但如果你在写的时候不小心把内循环的变量名搞混很容易变成“只检查了列没检查行”。我建议把行判断和列判断分开用两个独立的布尔变量表示“行最大”和“列最小”最后再合并判断。这样即便写错了也容易通过打印两个布尔变量来排查。第二提前break。暴力法里最常见的错误是找到第一个满足条件的鞍点后立刻break导致输出不完整。题目如果要求输出所有鞍点那你只能输出一个自然错误。即使题目只要求输出一个如果你在没有鞍点的情况下提前break也可能导致found标志没有被正确设置。我自己的习惯是除非题目明确写了“只输出第一个”否则一律遍历完整矩阵用found变量做统一判断。2.2 高效思路先求行最大值和列最小值再逐个验证另一种更稳妥、也更推荐的方法是预处理法。核心思想分三步用两个数组rowMax[5]和colMin[5]分别保存每一行的最大值和每一列的最小值。遍历一遍矩阵一边扫描一边更新这两个数组。再遍历第二遍矩阵判断每个元素是否等于它所在行的最大值且等于它所在列的最小值。由于每个元素既有行号又有列号所以判断条件很简单if (a[i][j] rowMax[i] a[i][j] colMin[j])。一旦相等就找到了一个鞍点。这种方法的时间复杂度是O(n^2)空间复杂度是O(n)。预处理法的另一个好处是逻辑极其清晰不容易漏。你不需要在每一个元素上重新扫描行和列只需要在预处理阶段各扫一次就够了。很多同学一开始不太习惯这种做法觉得“多开了两个数组有点浪费”。但实际上用空间换时间在算法竞赛和实际开发中非常常见也是很值得养成的习惯。我当年在SSE上先写的是暴力法结果在“全等矩阵”这个测试点上栽了。后来改成预处理法逻辑一遍就顺了只花了一点时间处理输出格式问题。如果你现在刚开始刷题我强烈建议直接按预处理法写省得后面还要改。2.3 时间复杂度与极端情况分析这道题n5无论暴力还是预处理运行时间都趋近于0。但我们为什么要关心复杂度因为SSE题库后面的题会逐渐加大规模。比如第40题可能变成“NxN矩阵找鞍点”n可能到100甚至更大。暴力法的O(n^3)在n100时是100万次操作虽然也不算太大但预处理法的O(n^2)只有1万次操作两者差距会越来越明显。更重要的是预处理法的代码结构本身就是一个“先统计、后匹配”的模板这种模板可以迁移到很多二维矩阵问题里。极端情况方面最需要注意的是“全等矩阵”。假设5x5矩阵所有元素都是同一个值比如全部是7那么每个元素都满足“所在行最大”和“所在列最小”所以每个位置都是鞍点。如果题目要求输出所有鞍点你必须输出25个坐标。如果你在之前的循环里设置了“找到一个就停止”那就只能输出一个必然错误。另一个极端情况是“完全不存在鞍点”。比如矩阵1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5这里每行的最大值是5但5所在的那一列即第5列最小值是5所以位置(0,4)等其实是鞍点。要构造无鞍点的矩阵需要让每一行的最大值位置都不对应所在列的最小值。比如5 4 3 2 1 5 4 3 2 1 ...第一行最大值5在列0但列0的最小值也是5所以还是有鞍点。最简单无鞍点的构造是让第一行最大值在第一列而第一列的最小值在另一行同时那另一行的最大值又不在这第一列……这类构造需要动点脑筋但作为边界测试非常有必要。3. C语言实现详解3.1 完整代码与逐段注释下面给出一个基于预处理法的完整C语言实现。代码里包含了stdio.h和limits.h两个头文件使用ANSI C注释风格尽可能兼容SSE的老式GCC环境。#include stdio.h #include limits.h int main() { int a[5][5]; int rowMax[5], colMin[5]; int i, j; int found 0; /* 输入矩阵 */ for (i 0; i 5; i) { for (j 0; j 5; j) { scanf(%d, a[i][j]); } } /* 初始化用每行每列的第一个元素代替“无穷大/无穷小” */ for (i 0; i 5; i) { rowMax[i] a[i][0]; colMin[i] a[0][i]; } /* 第一次遍历更新行最大值和列最小值 */ 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]); found 1; } } } if (!found) { printf(NO SADDLE POINT\n); } return 0; }这段代码的核心逻辑只有三大块输入、预处理、匹配。其中预处理那一块是重中之重。你要特别注意rowMax[i]和colMin[j]的下标——rowMax的下标是行号colMin的下标是列号不能搞混。很多同学会写错成rowMax[j]这在小矩阵测试时可能碰巧没问题因为5x5的行数列数恰好相等但一旦改成n x m矩阵就会立刻出错。另外found标志位非常重要。如果没有这个变量整个程序会进入if (!found)分支输出一个不存在的提示信息导致结果判定错误。我习惯在写完匹配循环后先顺手加上found 1;避免后面忘记。3.2 为什么需要stdio.h和limits.h题目提示里明确说了“使用stdio.h和limits.h”。stdio.h很好理解因为scanf和printf都在里面。但limits.h并不是这道题的硬性需求因为我们用第一个元素初始化实际上用不到limits.h里面的宏。那为什么要在代码里带上它呢主要是为了提醒自己思考“int类型能表示的最小值和最大值”。如果你用INT_MIN初始化rowMax、用INT_MAX初始化colMin就需要这个头文件。例如#include limits.h int rowMax[5], colMin[5]; for (i 0; i 5; i) { rowMax[i] INT_MIN; colMin[i] INT_MAX; }这种初始化方式的逻辑也没有问题但会失去“用第一个元素初始化”带来的简洁性。而且在部分老旧的编译器里如果代码中使用INT_MIN这个宏它大概会被展开为一个比较奇怪的表达式比如(-2147483647 - 1)这本身没有问题但有些教学平台的静态检查工具会给出警告。所以我更推荐第一种初始化方式用每行每列的第一个元素。这样既安全又不需要依赖limits.h。不过既然题目要求带上你完全可以包含它但不使用任何宏这不影响编译。3.3 输入输出格式的陷阱SSE平台对输出格式的敏感程度远超我原本的想象。同样是鞍点问题不同版本的题目可能要求printf(%d %d %d\n, i, j, a[i][j])用空格隔开坐标和值。printf(%d %d\n, i, j)只输出坐标。printf(a[%d][%d]%d\n, i, j, a[i][j])带花括号或方括号。如果不存在可能要求输出NONE、NO SADDLE POINT、not found等等。这里唯一可靠的解法是打开题目原文把最后的“输出格式”部分复制下来严格按照里面的占位符和字符串写。不要凭感觉造格式。我在一次机试中吃过亏题目要求输出x y value结果我多打了一个冒号变成x:y:value整题零分。另外要注意换行如果存在多个鞍点每个鞍点必须单独占一行。最后一个鞍点输出后也要换行这点和大多数OJ类似。如果不存在鞍点输出提示后也必须换行。你可以把提示字符串末尾的\n看成是不可省略的格式组成部分。4. 常见错误与调试经验4.1 用break提前结束导致漏判我最早写这道题时采用的暴力法代码如下错误版本for (i 0; i 5; i) { for (j 0; j 5; j) { /* 判断行最大 */ int isRowMax 1; for (k 0; k 5; k) { if (a[i][k] a[i][j]) { isRowMax 0; break; } } if (!isRowMax) continue; /* 判断列最小 */ 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]); break; /* 这里有问题 */ } } }这个错误版本的问题是break只跳出了内层循环但如果你把break放在匹配后的printf后面确实会提前结束整个双重循环导致只输出第一个鞍点。题目如果只要求输出第一个这还能通过但如果要求输出所有鞍点就会WA。更危险的是如果你在遇到第一个候选者时并没有继续检查后面的候选者你可能会漏掉一个真正的鞍点而把错误地当作“没有鞍点”处理。解决方法是不要在匹配后使用break而是增加一个found标志位并且让循环完整执行。如果你想提前退出应该使用一个统一的变量比如hasSaddle并在循环条件或外层设置if (hasSaddle) break;但这意味着你要确认题目允许你提前退出。为了保险起见我建议统一走“完整遍历”路线哪怕多输出几个也不会错。4.2 行最大值与列最小值的优先级另一个常见错误是对行最大值和列最小值的判断顺序不同导致结果不同。设想一个位置既是行最大又是列最小这当然是鞍点。但如果某一行有一个值既是最大值同时在这一列并不是最小值那么它不是鞍点。反之如果某一列有一个值是最小值但所在行不是最大值也不是鞍点。很多人写代码时会先给rowMax[i]赋一个超大值然后发现不对又改成INT_MIN。这里面最隐蔽的问题是你在更新rowMax[i]时使用if (a[i][j] rowMax[i]) rowMax[i] a[i][j];但在更新colMin[j]时如果忘记初始化colMin它默认是0则所有正的列最小值都无法被记录。所以初始化的位置一定要和定义放在一起并且每行每列都要初始化。我在调试时最喜欢打印数组rowMax和colMin看一眼就知道是不是初始化错了。4.3 当矩阵没有鞍点时输出什么“没有鞍点”并不是一种罕见情况但很多同学写的程序在没有找到鞍点时什么也不输出这种情况下SSE会根据输出差异直接判WA。正确做法是用found布尔变量标记是否找到了至少一个鞍点循环结束后判断found 0然后输出题目要求的“无鞍点”提示字符串。不要使用“最后再判断循环是否正常结束”这种技巧来判断是否找到鞍点。因为一旦使用了break循环结束方式就不是唯一的。尽可能让逻辑直白found初始为0每找到一个鞍点就置为1最后统一判断。我自测时通常会准备三组输入有唯一鞍点比如1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9这个矩阵里第一行的最大值是5但第5列的最小值是5所以(0,4)是鞍点然后再看其他行第5列都是5,6,7,8,9最小值确实是5所以(0,4)是鞍点。这组数据能验证基本逻辑。有多个鞍点比如全等矩阵3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3这组数据能验证你是否漏掉多个输出。无鞍点比如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第一行最大值5在第4列但第4列最小值是5所以(0,4)是鞍点似乎还是存在。要构造无鞍点需要让每行最大值所在列的最小值不是它本身。我们可以用9 8 7 6 5 8 7 6 5 4 7 6 5 4 3 6 5 4 3 2 5 4 3 2 1这个矩阵的第0行最大值是9在第0列第0列最小值是5在第4行但第4行的最大值是5在第0列所以(4,0)可能是鞍点第4行最大值5第0列最小值5所以(4,0)确实是鞍点。要真正无鞍点比较难构造但测试时你可以用一个随机生成的矩阵只要没有同时满足条件的元素即可。重点是代码中不能假设一定存在鞍点。4.4 本地测试与平台环境的差异如果本地编译器是VS或新版GCC一切都好说。但SSE平台可能用的还是老版本编译器不严格支持C99的某些特性比如变长数组。为了保险我用定长数组a[5][5]而不是通过变量声明a[n][n]。另外注释风格尽量用/* */虽然//在C99中合法但老规矩还是用兼容性最好的写法。还有一个老生常谈的问题如果scanf没有正常读入数据程序会卡住或读到非法值。你可以这样写for (i 0; i 5; i) { for (j 0; j 5; j) { if (scanf(%d, a[i][j]) ! 1) { return 1; } } }虽然第34题基本不会出现输入缺失但这个习惯能避免在后续多组输入的题目中出错。5. SSE平台的提交技巧与扩展思考5.1 提交前必做的三件事第一确认输出格式。把题目原文里的“输出说明”复制到一个记事本里然后用代码模板逐字比对。不要相信本地输出的格式一定和OJ一致。我吃过的亏是本地printf用%d\n但OJ要求%d %d\n结果整题WA。第二确认行列编号。有的题从0开始有的从1开始。我的办法是在测试用例里手动构造一个只有唯一鞍点的矩阵然后看输出坐标是否和预期一致。如果预期是“第2行第3列”而程序输出“1 2”那就说明编号有偏差。第三确认是否存在多组数据。如果题目说“输入到EOF结束”那么你的scanf必须放在while循环里而不是写死一组。第34题我遇到的基本是单组输入但提前写好while (scanf(...))也能兼容多组。注意在处理多组时rowMax和colMin需要在每一轮重新初始化否则上一组的结果会污染下一组。5.2 从鞍点问题到通用矩阵算法鞍点问题虽然简单但背后的“先求聚合值再逐点匹配”思路可以迁移到很多场景。比如以后做“矩阵中的幸运数”题目要求找出既是行最小又是列最大的元素其实做法一模一样只是把最大/最小互换。再比如“图像降噪”里的中值滤波需要先对每个像素周围邻域排序也是先做某种聚合再匹配。如果你能把这道题的代码封装成函数int findSaddlePoints(int matrix[][5], int rows, int cols, int results[][3])那你的代码复用能力会明显提升。SSE后半段有不少课设题目都要求“模块化设计”提前练习函数封装没坏处。5.3 我提交了十几遍总结出的流程先给结论不要一上来就写代码。先用笔在纸上画一个5x5矩阵手动标出可能的鞍点再对照代码逻辑推演一遍。这个“手动演算”的过程能帮你发现很多隐藏问题比反复编译强得多。然后写代码。本地用dev-C或VS Code都行但建议打开编译器的“警告”选项比如gcc的-Wall。如果有警告优先解决不要忽略。我第一次写这题时没开-Wall结果colMin[j]未初始化导致一堆莫名其妙的结果开了警告后立刻看出“可能未初始化”。最后提交。如果WA不要急着改代码先打印调试信息。可以临时加一行printf(rowMax[%d]%d colMin[%d]%d\n, i, rowMax[i], j, colMin[j]);看预处理的结果是否符合预期。这种调试方法虽然土但在OJ上也能用前提是你在提交前把调试输出删掉否则平台会把你打印的调试信息也当成答案的一部分。我个人在实际操作中的体会是这道题真正卡人的地方不在于算法而在于“严谨性”。它要求你同时考虑行和列考虑初始值考虑多个答案考虑无答案的情况——任何一个细节没照顾到都会让你陷入漫长的试错循环。后来我再碰到矩阵类题目都会先条件反射地问自己初始化用第一个元素了吗循环里有没有不合理的break输出格式和题目逐字核对了吗这三问帮我少走了很多弯路也希望你觉得有用。