现给定邻域参数 r 和阈值 t，试统计输入灰度图像中有多少像素处于较暗区域。
输入格式
输入共 n+1 行。
输入的第一行包含四个用空格分隔的正整数 n、L、r 和 t，含义如前文所述。
第二到第 n+1 行输入矩阵 A。
第 i+2
（
0
≤
i
<
n
）
（0≤i<n）
（0≤i<n）行包含用空格分隔的 n 个整数，依次为
A
i
0
,
A
i
1
,
⋯
,
A
i
(
n
−
1
)
A_{i0},A_{i1},⋯,A_{i(n−1)}
Ai0,Ai1,⋯,Ai(n−1)。
输出格式
输出一个整数，表示输入灰度图像中处于较暗区域的像素总数。
样例输入
4 16 1 6
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
样例输出
7
样例输入
11 8 2 2
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 7 0 0 0 7 0 0 7 7 0
7 0 7 0 7 0 7 0 7 0 7
7 0 0 0 7 0 0 0 7 0 7
7 0 0 0 0 7 0 0 7 7 0
7 0 0 0 0 0 7 0 7 0 0
7 0 7 0 7 0 7 0 7 0 0
0 7 0 0 0 7 0 0 7 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
样例输出
83
评测用例规模与约定
70% 的测试数据满足 n ≤ 100 n≤100 n≤100、 r ≤ 10 r≤10 r≤10。
全部的测试数据满足 0 < n ≤ 600 0<n≤600 0<n≤600、 0 < r ≤ 100 0<r≤100 0<r≤100 且 2 ≤ t < L ≤ 256 2≤t<L≤256 2≤t<L≤256。
题中要点共有三个：
求：矩阵A中邻域均值小于等于t的所有点的个数
由此我们很容易就可以得到解题思路：==把所有点的邻域均值求出来，与t比较判断就得出了答案。==但能不能拿满分的关键在于求均值的过程应该如何实现，因为这种题如果用死方法去一次一次地遍历算是很容易运行超时的。但没有更好思路的时候，先从最基本的方法开始实现也许会在过程中产生更好的想法，并且也可以先拿到一部分的分数。
下面我们先从最基本的方法开始实现，再在此基础上进行优化算法。
矩阵A我们通过一个二维数组来实现，注意此处应该使用double类型，因为计算均值涉及到除法，精度不够很可能会导致结果错误。
外层循环肯定是对整个数组进行遍历，内部进行每一个点邻域均值的计算。
首先应确定当前点的邻域范围，再对其内部进行求均值，此处应该考虑到边界的情况。（这里我直接用三目运算符看起来舒服点，用if也都是一样的）
//对于A[i][j],确定邻域范围：
//确定邻域的上下边界
int up = (i-r<0) ? 0 : (i-r);
int down = (i+r>n-1) ? (n-1) : (i+r);
//确定邻域的左右边界
int right = (j+r>n-1) ? (n-1) : (j+r);
int left = (j-r<0) ? 0 : (j-r);
确定边界后，对其中所有点求和再求均值，然后判断是否小于等于阈值，计数。
完整代码如下：
#include<cstdio>
double a[601][601] = {0};
int main() {
int n, r;
double L, t;
scanf("%d %lf %d %lf", &n, &L, &r, &t);
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
scanf("%lf", &a[i][j]);
}
}
int count = 0;
for(int i=0; i<n; i++) {
//确定邻域的上下边界
int up = (i-r<0) ? 0 : (i-r);
int down = (i+r>n-1) ? (n-1) : (i+r);
for(int j=0; j<n; j++) {
//确定邻域的左右边界
int right = (j+r>n-1) ? (n-1) : (j+r);
int left = (j-r<0) ? 0 : (j-r);
double sum = 0;
for(int p=up; p<=down; p++) {
for(int q=left; q<=right; q++) {
sum += a[p][q]; //邻域内所有数求和
}
}
double cr = (double)down-up+1;
double cl = (double)right-left+1;
double average = sum/(cr*cl); //求均值
if(average<=t) count++;
}
}
printf("%d", count);
return 0;
}
果然，运行超时，只有70分，说明解题思路是正确的，但是数据较大时会运行超时。这时我们对于程序主体是不用大改的，应该寻找程序的多重循环中哪里可以优化，减少执行次数。
回顾一下上面的程序，可以确定的是外层循环，即遍历整个矩阵，求每一个点的邻域均值是不能再优化的，因为要求满足要求的点的个数，必须要计算每一个点的邻域均值，那么就需要去优化内部求均值的过程。
在求均值的过程中，上面我们是对每一个邻域内的点都遍历一边求和再计算均值的，这样确实执行次数非常多，并且我们很容易发现各个相邻的邻域中有很多点都是重复的，每一次都重新计算总和很浪费时间。所以我们应该利用这些重复的部分来减少循环次数。
以样例1为例，我们可以看到，如果求的是
A
[
2
]
[
2
]
A[2][2]
A[2][2]的邻域内总和（即下图中红色矩形中的总和），其实可以看成是最外层的大矩形内总和，减去相邻两个小矩形内的总和。依次类推，所有的邻域都可以用这种方法来计算。
因此，这里我们可以通过前缀和的方法来对二维数组先进行预处理，将每个
A
[
i
]
[
j
]
A[i][j]
A[i][j]的值计算为从最左上角的
A
[
0
]
[
0
]
A[0][0]
A[0][0]到
A
[
i
]
[
j
]
A[i][j]
A[i][j]的一个矩形内的所有数之和。（以上图样例1为例，
A
[
3
]
[
3
]
A[3][3]
A[3][3]即为
0
+
1
+
2
+
3
+
.
.
.
+
15
0+1+2+3+...+15
0+1+2+3+...+15）。
然后在计算邻域内总和时，只需通过上面描述的方法即可快速求出结果，不必再对邻域内的数进行遍历。
//对于A[i][j],确定邻域范围：
//确定邻域的上下边界
int up = (i-r<0) ? 0 : (i-r);
int down = (i+r>n-1) ? (n-1) : (i+r);
//确定邻域的左右边界
int right = (j+r>n-1) ? (n-1) : (j+r);
int left = (j-r<0) ? 0 : (j-r);
double sum = a[down][right] - a[down][left-1] - a[up-1][right] + a[up-1][left-1];
然后我还在整个矩阵的外围补了0，以方便计算，就无需对边界情况进行额外的特殊处理。
最后完整的满分代码如下：
#include<cstdio>
double a[601][601] = {0};
int main() {
int n, r;
double L, t;
scanf("%d %lf %d %lf", &n, &L, &r, &t);
//从下标1开始输入，即给矩阵外围补了一圈0，方便下面计算前缀和，无需考虑边界情况
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
scanf("%lf", &a[i][j]);
}
}
//求出每个点a[i][j]坐标为边界的i*j的矩阵内元素值的总和
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
}
}
int count = 0;
for(int i=1; i<=n; i++) {
//确定邻域的上下边界
int up = (i-r<1) ? 1 : (i-r);
int down = (i+r>n) ? n : (i+r);
for(int j=1; j<=n; j++) {
//确定邻域的左右边界
int right = (j+r>n) ? n : (j+r);
int left = (j-r<1) ? 1 : (j-r);
//求均值
double sum = a[down][right] - a[down][left-1] - a[up-1][right] + a[up-1][left-1];
double cr = (double)down-up+1;
double cl = (double)right-left+1;
double average = sum/(cr*cl);
if(average<=t) count++;
}
}
printf("%d", count);
return 0;
}
