题目背景
顿顿在学习了数字图像处理后，想要对手上的一副灰度图像进行降噪处理。不过该图像仅在较暗区域有很多噪点，如果贸然对全图进行降噪，会在抹去噪点的同时也模糊了原有图像。因此顿顿打算先使用邻域均值来判断一个像素是否处于较暗区域，然后仅对处于较暗区域的像素进行降噪处理。
问题描述
待处理的灰度图像长宽皆为$n$个像素，可以表示为一个$n×n$大小的矩阵A，其中每个元素是一个$[0,L)$范围内的整数，表示对应位置像素的灰度值。
对于矩阵中任意一个元素$A_{ij}（0≤i,j<n）$，其邻域定义为附近若干元素的集和：
$$
Neighbor(i,j,r)={A_{xy}|0≤x,y<n\ and\ |x−i|≤r\ and\ |y−j|≤r}
$$
这里使用了一个额外的参数$r$来指明$A_{ij}$附近元素的具体范围。根据定义，易知$Neighbor(i,j,r)$最多有$(2r+1)^2$个元素。
如果元素$A_{ij}$邻域中所有元素的平均值小于或等于一个给定的阈值$t$，我们就认为该元素对应位置的像素处于较暗区域。
下图给出了两个例子，左侧图像的较暗区域在右侧图像中展示为黑色，其余区域展示为白色。
![]()
现给定邻域参数r和阈值t，试统计输入灰度图像中有多少像素处于较暗区域。
输入格式
输入共$n+1$行。
输入的第一行包含四个用空格分隔的正整数$n、L、r$和$t$，含义如前文所述。
第二到第$n+1$行输入矩阵$A$。
第$i+2（0≤i<n）$行包含用空格分隔的$n$个整数，依次为$A_{i0},A_{i1},⋯,A_{i(n−1)}$。
输出格式
输出一个整数，表示输入灰度图像中处于较暗区域的像素总数。
样例1输入
1
2
3
4
5
| 4 16 1 6
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
|
样例1输出
样例2输入
1
2
3
4
5
6
7
8
9
10
11
12
| 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
|
样例2输出
数据范围
70%的测试数据满足$n≤100、r≤10$。
全部的测试数据满足$0<n≤600、0<r≤100$且$2≤t<L≤256$。
解答（Dev-CPP 环境）
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <iostream>
using namespace std;
int a[605][605],sum[605][605];
int jmax(int x,int y){
return x>y?x:y;
}
int jmin(int x,int y){
return x<y?x:y;
}
int main(){
int ans=0;
int n,L,r,t;
cin>>n>>L>>r>>t;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
double avg,num;
int x1,x2,y1,y2;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
x1=jmax(1,i-r);
y1=jmax(1,j-r);
x2=jmin(n,i+r);
y2=jmin(n,j+r);
num=(x2-x1+1)*(y2-y1+1);
avg=(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1])*1.0/num;
if(avg<=t){
ans++;
}
}
}
cout<<ans;
return 0;
}
|
