时间轴 网站模板,百度广告费用,大连的网站制作公司,wordpress 微信内登录CSP-202104-2-邻域均值
关键点#xff1a;二维前缀和数组
详见#xff1a;
【CSP考题扩展】前缀和/差分练习【CSP考点回顾】二维前缀和数组#xff08;代码实现#xff09;
解题思路
1.输入和初始化
首先#xff0c;程序从输入中获取四个整数n#xff08;矩阵的大小…CSP-202104-2-邻域均值
关键点二维前缀和数组
详见
【CSP考题扩展】前缀和/差分练习【CSP考点回顾】二维前缀和数组代码实现
解题思路
1.输入和初始化
首先程序从输入中获取四个整数n矩阵的大小L像素亮度的上限r局部区域的半径和t暗像素判定阈值。初始化一个n x n的二维数组pic来存储输入的图像数据每个像素的亮度值。
2.构建二维前缀和数组 初始化前缀和数组 首先initPrefixSum函数创建一个大小为(n1) x (n1)的新数组prefixSum所有元素初始化为0。这个大小比原图像多一行和一列是为了方便边界情况的处理避免在计算时出现索引越界。这个额外的行和列代表的是边界外的空区域其前缀和自然为0。 填充前缀和数组 然后函数遍历原始的图像数组pic。对于图像中的每个像素(i-1, j-1)因为我们的prefixSum是从1开始计数的所以原图像的第一个元素对应于prefixSum的(1, 1)更新prefixSum数组。更新规则如下prefixSum[i][j]的值等于当前元素matrix[i - 1][j - 1]即原图像的当前像素亮度值加上左侧元素的前缀和prefixSum[i][j-1]加上上方元素的前缀和prefixSum[i-1][j]再减去左上角元素的前缀和prefixSum[i-1][j-1]因为它被加了两次。通过这种方式每个prefixSum[i][j]代表了原始图像左上角到(i-1, j-1)形成的矩形区域的所有像素亮度之和。
3.判断暗像素 遍历图像中的每个像素 isDark函数用于确定一个像素是否“暗”。对于图像中的每个像素(i, j)函数计算以该像素为中心边长为2r1的局部区域内所有像素的平均亮度。要考虑边界条件即当像素位于图像的边缘时实际的局部区域可能小于2r1。因此实际的局部区域边界由max(0, i - r)、max(0, j - r)、min(n - 1, i r)和min(n - 1, j r)确定。 计算局部区域亮度平均值 使用前缀和数组可以快速计算局部区域的总亮度这是通过查询前缀和数组中相应角落的值并应用矩形区域和公式来完成的。计算该区域内的像素总数即(xEnd - xStart 1) * (yEnd - yStart 1)。计算平均亮度即区域总亮度除以区域内的像素总数。如果这个平均亮度小于或等于阈值t则认为中心像素是“暗”的。
4.统计和输出结果
在遍历过程中统计被认为是“暗”的像素的数量。最后输出“暗”像素的总数。
完整代码
【100分思路-前缀和数组】
#include iostream
#include vector
#include algorithm
using namespace std;int n, L, r, t, darkNum;
vectorvectorintpic, prefixSum;void initPrefixSum(vectorvectorint prefixSum, const vectorvectorint matrix) {int rows matrix.size();int cols matrix[0].size();prefixSum.resize(rows 1, vectorint(cols 1, 0));for (int i 1; i rows; i) {for (int j 1; j cols; j) {prefixSum[i][j] matrix[i - 1][j - 1] prefixSum[i - 1][j] prefixSum[i][j - 1]- prefixSum[i - 1][j - 1];}}
}int queryPrefixSum(const vectorvectorint prefixSum, int x1, int y1, int x2, int y2) {int sum prefixSum[x2 1][y2 1]- prefixSum[x1][y2 1]- prefixSum[x2 1][y1] prefixSum[x1][y1];return sum;
}bool isDark(int i, int j) {int xStart max(0, i - r), yStart max(0, j - r);int xEnd min(n - 1, i r), yEnd min(n - 1, j r);double sum queryPrefixSum(prefixSum, xStart, yStart, xEnd, yEnd);double num (xEnd - xStart 1) * (yEnd - yStart 1);double arg sum / num;return arg t;
}int main() {cin n L r t;pic vectorvectorint(n, vectorint(n, 0));for (auto it : pic) {for (auto jt : it) {cin jt;}}initPrefixSum(prefixSum, pic); // 构建二维前缀和数组for (size_t i 0; i pic.size(); i){for (size_t j 0; j pic[i].size(); j){if (isDark(i, j)) darkNum;}}cout darkNum;return 0;
}【70分思路-暴力枚举】
#include iostream
#include vector
#include algorithm
using namespace std;int n, L, r, t, darkNum;
vectorvectorintpic;bool isDark(int i, int j) {int xStart max(0, i - r), yStart max(0, j - r);int xEnd min(n - 1, i r), yEnd min(n - 1, j r);double num 0, sum 0;for (size_t x1 xStart; x1 xEnd; x1){for (size_t y1 yStart; y1 yEnd; y1){num;sum pic[x1][y1];}}double arg sum / num;return arg t;
}int main() {cin n L r t;pic vectorvectorint(n, vectorint(n, 0));for (auto it : pic) {for (auto jt : it) {cin jt;}}for (size_t i 0; i pic.size(); i){for (size_t j 0; j pic[i].size(); j){if (isDark(i, j)) darkNum;}}cout darkNum;return 0;
}
