邻域均值
题目背景
顿顿在学习了数字图像处理后，想要对手上的一副灰度图像进行降噪处理。不过该图像仅在较暗区域有很多噪点，如果贸然对全图进行降噪，会在抹去噪点的同时也模糊了原有图像。因此顿顿打算先使用邻域均值来判断一个像素是否处于较暗区域，然后仅对处于较暗区域的像素进行降噪处理。
问题描述
待处理的灰度图像长宽皆为n个像素，可以表示为一个n×n大小的矩阵A，其中每个元素是一个[0,L)范围内的整数，表示对应位置像素的灰度值。
对于矩阵中任意一个元素Aij（0≤i,j<n），其邻域定义为附近若干元素的集和：
Neighbor(i,j,r)={Axy|0≤x,y<n and |x−i|≤r and |y−j|≤r}
这里使用了一个额外的参数r来指明Aij附近元素的具体范围。根据定义，易知Neighbor(i,j,r)最多有(2r+1)2个元素。
如果元素Aij邻域中所有元素的平均值小于或等于一个给定的阈值t，我们就认为该元素对应位置的像素处于较暗区域。
下图给出了两个例子，左侧图像的较暗区域在右侧图像中展示为黑色，其余区域展示为白色。
现给定邻域参数r和阈值t，试统计输入灰度图像中有多少像素处于较暗区域。
输入格式
输入共n+1行。
输入的第一行包含四个用空格分隔的正整数n、L、r和t，含义如前文所述。
第二到第n+1行输入矩阵A。
第i+2（0≤i<n）行包含用空格分隔的n个整数，依次为Ai0,Ai1,⋯,Ai(n−1)。
输出格式
输出一个整数，表示输入灰度图像中处于较暗区域的像素总数。
样例1输入
4 16 1 6
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
样例1输出
7
样例2输入
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
样例2输出
83
数据范围
70%的测试数据满足n≤100、r≤10。
全部的测试数据满足0<n≤600、0<r≤100且2≤t<L≤256。
题解
要求一个邻域内所有元素的平均值，首先要求所有元素的和
于是我们可以求矩阵前缀和，对于每个元素用O(1)的时间求和，再求平均值
确定邻域的范围的时候，还要注意邻域范围不能超过整个灰度图像的范围
1 #include <cstdio> 2 int n,L,r,a[605][605],sum[605][605],ans; 3 double t; 4 int mmax(int x,int y) 5 { 6 return x>y?x:y; 7 } 8 int mmin(int x,int y) 9 { 10 return x<y?x:y; 11 } 12 int main() 13 { 14 int i,j; 15 scanf("%d%d%d%lf",&n,&L,&r,&t); 16 for (i=1;i<=n;i++) 17 for (j=1;j<=n;j++) 18 scanf("%d",&a[i][j]); 19 for (i=1;i<=n;i++) 20 sum[1][i]=sum[1][i-1]+a[1][i], 21 sum[i][1]=sum[i-1][1]+a[i][1]; 22 for (i=2;i<=n;i++) 23 for (j=2;j<=n;j++) 24 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; 25 double rr; 26 int x1,y1,x2,y2; 27 for (i=1;i<=n;i++) 28 for (j=1;j<=n;j++) 29 { 30 x1=mmax(i-r,1); y1=mmax(j-r,1); 31 x2=mmin(i+r,n); y2=mmin(j+r,n); 32 rr=(x2-x1+1)*(y2-y1+1); 33 if ((sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1])*1.0/rr<=t) 34 ans++; 35 } 36 printf("%d",ans); 37 return 0; 38 }