领域均值
题目：
待处理的灰度图像长宽皆为 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)。
输出格式
输出一个整数，表示输入灰度图像中处于较暗区域的像素总数。
样例输入
样例输出
样例输入
样例输出
#include <iostream> using namespace std; //n为待处理像素个数，r为元素范围，L为灰度值的最大值，t为给定的阈值 int main() { int n,L,r,t,res = 0; cin>>n>>L>>r>>t; int a[n][n],s[n][n];//a为原始数组，s为一维前缀数组 for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin>>a[i][j]; if(j == 0) s[i][j] = a[i][j]; //第一列为原本数据 else s[i][j] = s[i][j-1] + a[i][j];//第二列之后为该数据与其前面数据的和 } } int le,ri,hi,lo,sum,num;//分别为，左边界，右边界，上界，下界，区域内元素和，元素个数 for(int i = 0; i < n; i++){ if(i < r) hi = 0; else hi = i-r; //确定上界 if(n-i-1 < r) lo = n-1; else lo = i+r; //确定下界 for(int j = 0; j < n; j++){ if(j < r) le = 0; else le = j-r; if(n-j-1 < r) ri = n-1; else ri = j+r; //对每个元素对应的左右边界进行确定 num = (lo-hi+1)*(ri-le+1); //确定元素个数 sum = 0; for(int k = hi; k <= lo; k++){ sum += s[k][ri] - s[k][le] + a[k][le]; //利用前缀和求出每一行的和 } if(sum*1.0/num <= t*1.0) res++; //计算处于较暗区域的点的个数 } } cout<<res; return 0; }
方法二：二维前缀和
#include <iostream> using namespace std; int main() { int n,L,r,t,res = 0; cin >> n >> L >> r >> t; int a[n][n]; int s[n][n]; //初始化a,s for(int i = 0; i < n; i++){ for(int j = 0; j < n;j++){ cin >> a[i][j]; if(i == 0 && j == 0) s[i][j] = a[i][j]; else if(i == 0) s[i][j] = s[i][j-1] + a[i][j]; else if(j == 0) s[i][j] = s[i-1][j] + a[i][j]; else s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]; } } int le,ri,hi,lo,num,sum; for(int i = 0;i < n;i++){ //确定上下界 if(i - r < 0) hi = 0; else hi = i - r; if(n - 1 - i < r) lo = n-1; else lo = i + r; for(int j = 0; j < n; j++){ //确定左右边界 if(j < r) le = 0; else le = j - r; if(j + r > n-1) ri = n-1; else ri = j + r; num = (ri - le + 1) * (lo - hi + 1); if(hi == 0 && le == 0) sum = s[lo][ri]; else if(hi == 0) sum = s[lo][ri] - s[lo][le-1]; else if(le == 0) sum = s[lo][ri] - s[hi-1][ri]; else sum = s[lo][ri] - s[hi-1][ri] - s[lo][le-1] + s[hi-1][le-1]; if(sum*1.0/num <= t*1.0) res++; } } cout << res; return 0; }
原理图：