跟集训队的小朋友讲这道题的时候我问过一个特别直接的问题这道题到底难在哪有人说难在四舍五入有人说难在边界还有人直接说没读懂题。其实题目本身不长就是 OpenJudge NOI 1.8 13 和《信息学奥赛一本通》1128 都在考的这道“图像模糊处理”给一个 n 行 m 列的灰度图像把每个非边界像素变成它自己和上下左右五个像素灰度值的平均值四舍五入到整数边界像素保持原样。听起来像是一个二重循环就能解决的问题但每次课堂上总有一半以上的人第一次提交 WA。为什么因为这道题表面上考二维数组遍历实际上在考你三个特别容易被忽略的细节边界处理、平均值精度、原数组的覆盖顺序。这篇文章我会从题目本质讲起把每一步为什么这么做讲透再给出一份可以直接照着写的 C 主流程代码最后用几个自测用例帮你提交前把雷先踩一遍。适合刚学完二维数组、准备刷 OpenJudge 或者打信息学竞赛基础的同学。1. 题目到底在考什么很多初学者没看透的“二维数组基本功”先说清楚题目要我们做什么。给定一个 n 行 m 列的整数矩阵每个位置表示一个像素点的灰度值。对于不在边界上的像素点新灰度值等于它自身加上正上方、正下方、正左方、正右方这五个灰度值的平均结果要四舍五入。边缘上的点没有完整的“上下左右”邻居所以不参与运算保持原样输出。很多同学一看到“图像”“像素”“灰度值”就觉得这是某种高深图像处理直接被吓住了。拆掉这些名词它就是一个二维整数数组的邻域求和问题。你在初中数学里学过平面直角坐标系一个二维数组也可以看成一张坐标网格行号 i 是纵坐标列号 j 是横坐标。每个像素点的位置用(i, j)表示那么它的上下左右邻居分别是(i-1, j)、(i1, j)、(i, j-1)、(i, j1)。这样一来取“上下左右”就不再是玄学而是给当前坐标的一组固定偏移量。1.1 邻域取值的本质从像素到坐标系这道题的核心操作可以写成下面这段结构sum a[i][j] sum a[i-1][j] // 上 sum a[i1][j] // 下 sum a[i][j-1] // 左 sum a[i][j1] // 右 avg round(sum / 5.0)如果你和我一样习惯了从 0 开始编号那么对于第 i 行第 j 列的格子四个方向的偏移就是上方行号减 1列号不变即(-1, 0)下方行号加 1列号不变即(1, 0)左方行号不变列号减 1即(0, -1)右方行号不变列号加 1即(0, 1)这四个偏移量组合在一起就是很多算法题里说的“方向数组”。以后你写迷宫搜索、广度优先遍历、深度优先遍历还是会遇到完全一样的套路。所以如果你现在能把上下左右偏移数组写熟练后面学搜索会轻松很多。用方向数组的好处是代码清爽不容易漏项。但要注意这道题里“中心点自己”也算在求和里所以初始化sum时候要先放a[i][j]然后再循环累加四个方向。不是只加邻居。1.2 隐藏的考点保存原值、边界和四舍五入如果你只是想把功能跑通二重循环加一个 if 判断就能写。但竞赛评测不看功能它只看结果和性能。这道题结果上设置了三个关卡。第一计算平均时必须基于原始图像数据。如果边算边在原数组上覆盖那么你算完一个点之后它旁边的点再算的时候可能已经读到了“模糊后的值”而不是“模糊前的值”。这就像你用美图软件处理照片处理到一半把中间结果保存回原文件后续像素参考的就是被处理过的污染数据。第二边界像素必须保留原值。这里不要自己脑补“对边界点做特殊模糊”题目说保持原样就保持原样。你只需要在遍历时跳过第一行、最后一行、第一列、最后一列也就是i从 1 到n-2j从 1 到m-2。第三平均值的四舍五入要处理对。C语言和 C 里的整数除法是直接截断小数部分比如8 / 5得到 1但8 / 5 1.6四舍五入应该是 2。如果你直接写sum / 5最后输出的结果会差出不少测试数据一旦专门设计了 .5 或 .6 的小数就会 WA。这三个问题只要有一个没解决提交结果就不会是满分。这就是为什么这道题虽然代码量不大却一直作为二维数组阶段的高频考题。2. 边界保持、平均值计算与覆盖顺序三个最容易丢分的细节2.1 边界像素为什么“不动”先看一个实际问题第一行第一列的那个格子它的上方和左方根本不存在。如果让所有像素都做同样的邻居平均就必须给边界像素定义一个“越界邻居”比如把越界部分当成 0或者复制边界值。题目为了降低难度直接规定边界不参与运算保留原值。这其实是图像处理里一种很常用的边界策略叫做“不做处理”。但从做对题的角度你要记住的是不要为了统一代码而把边界也拉进循环。我看到过有人用一大堆if (i 0) ...去判断每个方向是否存在虽然这样也能算但毫无必要而且边界值如果不小心被重新赋值照样 WA。正确做法是for (int i 1; i n - 1; i) { for (int j 1; j m - 1; j) { // 只处理 i 和 j 都在中间范围的点 } }这样循环天然跳过四个边代码既短又不会越界。很多老手一眼能看到这个循环范围就是因为他们已经形成条件反射涉及上下左右邻域时内层点从 1 到 n-2 / m-2。2.2 平均值怎么算才满足“四舍五入”这里有个很实际的问题如果直接用printf(%.0lf, avg)这种格式来四舍五入在不同编译器或者不同平台的实现上可能有细微差异而且还要引入浮点数。最简单稳妥的竞赛写法是用整数运算完成四舍五入。五个灰度值的和是sum平均值是sum / 5。因为都是非负整数四舍五入的规则可以这样理解余数是 0、1、2 时答案取整数部分余数是 3、4 时答案取整数部分加 1。用这个规则可以直接推出一个整数公式ans (sum 2) / 5;我们来验证几个常见情况sum 8真实平均数是 1.6四舍五入为 2(8 2) / 5 2。sum 7真实平均数是 1.4四舍五入为 1(7 2) / 5 1。sum 13真实平均数是 2.6四舍五入为 3(13 2) / 5 3。sum 12真实平均数是 2.4四舍五入为 2(12 2) / 5 2。为什么加 2 而不是加别的因为sum / 5的余数只有 0 到 4当余数大于等于 3 时需要进位。“加 2”相当于把原来的余数整体抬高一截然后整数除法自动把跨过 5 的那部分进上去。这个技巧在竞赛里很常见尤其适合这种分母固定的整数均值题。如果你用的是浮点数也可以写int(sum / 5.0 0.5)但要小心运行时如果sum / 5.0恰好出现类似 2.499999 的浮点误差结果可能不够稳定。能用整数公式就别依赖浮点。2.3 覆盖顺序为什么不能在原数组上直接改这是整道题最大的坑。假设原始数组叫a你边算边把a[i][j]改成新值。那么当你算到a[i][j1]时需要读取左邻居a[i][j]。可这时候a[i][j]已经不是原始灰度值而是刚才模糊完的结果。一步错后面的计算全都错。打个比方你在黑板上一行一行地写数字写完之后又要根据这一行的数字算平均值那你必须先把整行数字抄到另一张纸上然后再对着原版算。如果你一边算一边擦掉旧值写上平均值后面的人看到的就不是原来的数据了。对应到代码里有两个基本思路。思路一读入原始数组a再定义一个新数组b作为结果数组。所有模糊计算都读a写b最后输出b。思路二复制一份原始数组到tmp在原数组a上进行计算。也就是读tmp写a最后输出a。我比较推荐思路一因为语义清晰原始数据永远不变结果单独存放不容易搞混。你只需要在读完输入后把a复制到b然后只更新b的内层格子最后输出b。复制一份二维数组的代码量很小而且 100×100 的规模内存上完全不是问题。3. 参考实现与逐行解读一份能 AC 的 C 代码3.1 完整代码下面这份代码是 C 的用标准输入输出可以直接提交到 OpenJudge 或者对应的一本通在线评测平台。我特意用cstdio而不是cin/cout因为竞赛里输入数据量虽然不大但养成用scanf/printf的习惯能减少不少 IO 性能问题。#include cstdio int a[105][105]; int b[105][105]; int main() { int n, m; scanf(%d %d, n, m); for (int i 0; i n; i) { for (int j 0; j m; j) { scanf(%d, a[i][j]); } } // 先复制一份原始图像到 b保证后续计算读到的都是原始值 for (int i 0; i n; i) { for (int j 0; j m; j) { b[i][j] a[i][j]; } } // 上下左右四个方向的偏移量 int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; // 只处理中间区域跳过边界 for (int i 1; i n - 1; i) { for (int j 1; j m - 1; j) { int sum a[i][j]; // 中心点自身 for (int k 0; k 4; k) { int ni i dx[k]; int nj j dy[k]; sum a[ni][nj]; } b[i][j] (sum 2) / 5; // 四舍五入取整数 } } for (int i 0; i n; i) { for (int j 0; j m; j) { if (j 0) { printf( ); } printf(%d, b[i][j]); } printf(\n); } return 0; }核心逻辑一共就三块读入并复制、计算中间区域、输出结果。你可以看到代码里sum的初始值直接放的是a[i][j]然后四个方向累加这样正好是题目要求的“自身加上下左右五像素”。代码最后处理输出时我用if (j 0) printf( );保证同一行数字之间用空格隔开最后一个数字后面没有多余空格这在某些严格判空格的题目里能帮你避免无谓的 Presentation Error。3.2 复杂度与数组大小的选择这个算法的复杂度是 O(n × m × 4)因为每个内层点最多访问 5 个原始数据。n 和 m 一般在 100 以内所以这个复杂度低到可以忽略不计。即使 n、m 到 1000这个写法也完全没有性能压力。数组大小我写的是105这是一种竞赛选手的习惯。因为题目如果给出 n, m 最大 100用a[100][100]其实也够用但稍微多开几个元素能避免一些边界意外比如某些题目下标从 1 开始读入时第 100 行第 100 列可能落在a[100][100]如果数组只开到[99]就越界了。多开 5 个单位是“安全余量”不丢人。如果你喜欢也可以用常量定义const int MAXN 105; int a[MAXN][MAXN];这样代码改起来更方便。信息学竞赛里数组开多大不是玄学而是根据题目给出上限再加一点余量。别开太大导致内存爆炸也别刚好卡在上限上。3.3 换到 Python / Java 时的注意点有些同学学校机房用的是 Python或者后续要参加 NOI 系列里允许 Python 的场合我也简单提一下区别。Python 读二维数组通常用列表推导式n, m map(int, input().split()) a [list(map(int, input().split())) for _ in range(n)] b [row[:] for row in a] # 深拷贝不能用 b a注意b a只是把新名字指向同一个列表修改b会同时改a这不是复制。使用[row[:] for row in a]才能逐行复制。计算平均时b[i][j] (sum 2) // 5Python 的//是向下取整但因为所有数据都是非负整数所以(sum 2) // 5的进位效果和 C 一样。Java 里复制二维数组可以用clone()但更不容易出错的是嵌套循环逐元素复制。用BufferedReader和StringTokenizer读整数可以避免Scanner在大输入下的性能问题但本题数据量小Scanner也没问题。关键是同样记住要么用两个数组要么把副本存好绝不能边算边改源数组。4. 自测用例与评测中的常见坑在提交前先拦住 WA4.1 三个值得手推的自测用例刷 Online Judge 题只跑样例远远不够。样例数据往往比较简单经常测不出覆盖顺序和四舍五入的问题。我推荐你提交前手动验证下面这样几组数据。第一组验证全图没有任何中间点的情况输入1 5 1 2 3 4 5因为 n1没有非边界点所有数字原样输出。这种极端输入最容易暴露你数组循环的越界问题。如果你的循环范围不判断n - 1 1就直接访问a[1][j]程序大概率崩溃。第二组验证四舍五入输入3 5 0 0 0 0 0 0 3 1 4 0 0 0 0 0 0手动计算一下。中间点(1, 1)的值是 3加上上 0、下 0、左 0、右 1总和是 4平均数是 0.8四舍五入为 1。中间点(1, 2)的值是 1加上上 0、下 0、左 3、右 4总和是 8平均数是 1.6四舍五入为 2。中间点(1, 3)的值是 4加上上 0、下 0、左 1、右 0总和是 5平均数是 1.0四舍五入为 1。所以输出应该是0 0 0 0 0 0 1 2 1 0 0 0 0 0 0如果你算出来的中间行是0 1 1 1 0说明你在平均值上用了整除把 1.6 截断成了 1。如果算出来是别的结果大概率是覆盖顺序出了问题。第三组验证边界保持输入4 4 1 1 1 1 1 5 5 1 1 5 5 1 1 1 1 1最外一圈全是 1四个中间点对称。每个中间点的上下左右里有两个邻居是 5两个邻居是 1自己也是 5总和为 5511517平均数是 3.4四舍五入为 3。所以输出应该是1 1 1 1 1 3 3 1 1 3 3 1 1 1 1 1这组数据同时验证了边界没有被改动以及四舍五入对3.4的处理。如果你的结果里四个 3 变成 2说明可能用了别的取整方式。4.2 输出格式和评测机制的细节OpenJudge 这类平台对输出格式的要求通常没有想象中那么死板行末多一个空格一般也能过。但在信息学竞赛里培养严格输出习惯从来不是坏事。我推荐统一采用“第一个数前面不空格之后的每个数前面加一个空格”的写法。这样输出的行末自然没有多余空格视觉上也整齐。还有一个小细节OpenJudge 的题目文件里读入的灰度值不保证都是个位数可能是 0 到 255 之间的整数。有人图省事把所有数都当成char去读结果负数或者大数就出问题。遇到像素灰度老老实实用int不要搞骚操作。另外数据规模虽然小但如果你不小心在题目要求多组输入的地方用了单组输入也会 RE 或 WA。这道题明确是一次性输入一组数据不需要 while 循环读 EOF不要画蛇添足。4.3 常见错误快查表我把自己在带训练时见过的高频错误整理成了一张表几乎能覆盖这道题 90% 的 WA 原因。错误类型典型表现原因修正方式原数组被覆盖输出结果中很多值偏大边算边改后续读到新值使用新数组 b 保存结果计算时始终读原始数组边界也参与计算第一行/最后一行的值变了循环范围写成了 0 到 n-1循环 i 从 1 到 n-2j 从 1 到 m-2平均值用整除1.6 被当成 1C/C 中 int/int 截断小数用(sum 2) / 5或浮点四舍五入输出格式错误PE 或行尾空格引发不必要扣分最后一个数后面多打空格用if (j 0) printf( );控制空格数组下标越界运行时崩溃边界条件判断不足先判断 n 和 m 是否足够大再访问邻域使用未复制的新数组直接更新结果里四角被改没理解“读原始数据写新数据”读入后先复制一份完整数据这张表不是让你背的而是让你提交前对照自查。如果 WA 了先问自己三个问题我是在原数组上直接改了吗我的循环范围真的跳过了边界吗我的5到底有没有参与四舍五入把这三个问完很多问题立刻就有答案了。5. 从“图像模糊”到更宽的算法视野方向数组的价值5.1 均值滤波图像降噪的入门形态你可能觉得“图像模糊处理”只是一道竞赛题但在真实图像处理里它的名字叫均值滤波。当一张照片有噪点时最简单粗暴的降噪方法就是把每个像素和它周围的像素平均一下让突变点被周围拉平。这个操作的窗口可以是一个十字形也可以是一个 3×3 方形甚至更大的 5×5 方形。窗口越大图像越模糊降噪越强但细节损失也越多。真实图像处理里像素值通常是 RGB 三通道每个通道分别做均值滤波。比赛题把它简化成单通道灰度图数据都是整数但仍然保留了均值滤波的核心思想用邻域信息修正当前像素。这道题做顺了以后接触 OpenCV、卷积神经网络、图像平滑你会觉得那些公式没那么神秘。5.2 从十字邻域到 3x3 卷积核如果题目不是五个点而是九个点呢也就是把左上、右上、左下、右下也纳入计算。你只需要改两组地方方向数组从 4 个方向变成 8 个方向求和的元素从 5 个变成 9 个边界范围依然是 1 到 n-2、1 到 m-2因为 3×3 窗口的最内层点同样不能落在边上。代码结构几乎不变。如果把方向数组再推广还能处理有权重的卷积核比如高斯模糊里中心点权重高、周围点权重低。这在代码上不过就是给每个方向配一个权重值累加时乘上对应权重最后除以总权重。你在这道题里学到的“把邻域规则抽成偏移数组”的思路是所有图像卷积操作的起点。更妙的是这个方向数组还能用于棋盘类搜索题。比如一个机器人从左上角走到右下角每一步可以向上下左右移动你判断下一步能不能走时就是用同样的dx、dy去生成候选坐标。所以不少老师喜欢拿这道题当“方向数组”的第一课不是没有原因。5.3 这道题还能怎么变想检验自己是不是真的吃透了可以试着改几个条件做扩展。第一把“边界保持不变”改成“边界用最近的边界值填充”。那你就要写额外的逻辑先处理角点、再处理四条边最后处理内部。第二把“一次模糊”改成“连续模糊 k 次”。这种情况下你需要两个数组交替使用也就是这一轮的结果作为下一轮的输入而不是每次都从最开始的原始数组算。第三把“平均值四舍五入”改成“平均值向下取整”。那只需要把(sum 2) / 5换成sum / 5但你要想清楚语义上是否真的合理。我的建议是每次做完一道题不要急着做下一道花五分钟想想“如果条件换个写法我原来的代码哪些地方必须跟着变”。这种举一反三的训练比盲目刷十道同类型题更有效。至少在我带过的学生里能把这道题做到“改两个参数就能应付三个变体”的人后面学广搜明显比只是背代码的人顺得多。说实话这道题的思路并不复杂难的是能不能把“原始数据”和“计算结果”分得清清楚楚。我每次让学生自己动手画一遍 3×3 的小格子把每个中间点对应的上下左右邻居用箭头标出来他们再写代码几乎不会再错。竞赛里很多题都是这样看似在考某个语法或者算法实际上考的是你有没有把过程在脑子里建模清楚。图像模糊处理是一道很好的练手题把这道题的细节一次想明白后面的二维数组题会轻松很多。