解题思路

这是一道“图像处理”的基础题，用二维数组模拟像素的模糊。

1. 什么是模糊？

黑白图像每个点叫“像素”，它的灰度值存在二维数组里。模糊就是把每个内部的点，用自己和周围 4 个邻居的平均值来代替，这样图像看起来就更“糊”。

2. 哪些点要变？

• 最外圈（第 1 行、第 n 行、第 1 列、第 m 列）不变；
• 内部的点：新值 =（自己 + 上 + 下 + 左 + 右）÷ 5，结果向下取整。

比如样例里第 2 行第 2 列的 100，它上下左右是 0、50、50、200：(100+0+50+50+200)÷5=400÷5=80。

3. 为什么要开两个数组？

如果直接在原数组上改，算第 2 个点的时候会用到已经被改过的邻居，结果就错了！所以先用 a 存原来的图，用 b 存模糊后的结果，全部算完再输出 b。

4. 向下取整怎么做？

C++ 里两个整数相除，结果是自动向下取整的，比如 7÷2=3。所以直接写 (a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j-1]+a[i][j+1])/5 就行。

参考代码

#include <iostream>
using namespace std;
int a[105][105], b[105][105];
int main(){
    // P4526 图像的模糊处理：四周像素不变，内部像素取自己和上下左右5个数的平均值（向下取整）
    int n, m;
    cin >> n >> m;
    // 读入原始图像
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin >> a[i][j];
    // 计算模糊后的图像存到 b 数组
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1 || i==n || j==1 || j==m)
                b[i][j] = a[i][j]; // 最外圈保持不变
            else
                // 自己 + 上 + 下 + 左 + 右 的平均值（整数除法自动向下取整）
                b[i][j] = (a[i][j] + a[i-1][j] + a[i+1][j] + a[i][j-1] + a[i][j+1]) / 5;
        }
    }
    // 输出结果
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout << b[i][j];
            if(j<m) cout << " "; // 数字之间用空格隔开
        }
        cout << endl;            // 每行结束换行
    }
    return 0;
}

复杂度分析

图像有 n 行 m 列，一共 n×m 个像素。我们要读入一次、计算一次、输出一次，每个像素都被访问了几次常数次，所以时间复杂度是 O(n×m)。题目说 1 ≤ n,m ≤ 100，最多 10000 个像素，非常快。

用了两个 105×105 的二维数组，空间复杂度是 O(n×m)。