B4451 [GESP202512 四级] 建造
题目描述
小 A 有一张MMM行NNN列的地形图，其中第iii行第jjj列的数字aija_{ij}aij代表坐标(i,j)(i, j)(i,j)的海拔高度。
停机坪为一个3×33 \times 33×3的区域，且内部所有999个点的最大高度和最小高度之差不超过HHH。
小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部999个点海拔之和最大是多少。
输入格式
第一行三个正整数M,N,HM, N, HM,N,H，含义如题面所示。
之后MMM行，第iii行包含NNN个整数ai1,ai2,…,aiNa_{i1}, a_{i2}, \dots, a_{iN}ai1,ai2,…,aiN，代表坐标(i,j)(i, j)(i,j)的高度。
数据保证总存在一个适合建造停机坪的区域。
输出格式
输出一行，代表最大的海拔之和。
输入输出样例 #1
输入 #1
5 5 3 5 5 5 5 5 5 1 5 1 5 5 5 5 5 5 5 2 5 2 5 3 5 5 5 2输出 #1
40说明/提示
数据范围
对于所有测试点，保证1≤M,N≤1031 \leq M, N \leq 10^31≤M,N≤103，1≤H,aij≤1051 \leq H, a_{ij} \leq 10^51≤H,aij≤105。
题解：建造
一、 解题思路
- 确定遍历对象：3×3区域的位置由其左上角坐标
(i,j)唯一确定，有效左上角坐标的行范围是1~m-2、列范围是1~n-2（该范围可保证3×3区域不超出地形图边界），遍历该范围内所有坐标即可覆盖所有潜在停机坪区域。 - 合法性校验：对每个左上角
(i,j)对应的3×3区域，遍历区域内9个点，找出最大海拔和最小海拔，判断两者差值是否不超过阈值H，满足条件则该区域合法。 - 计算海拔总和：对于合法的3×3区域，再次遍历区域内9个点，累加所有点的海拔高度，得到该区域的海拔总和。
- 维护全局最大值：定义全局变量
ans存储最终结果并初始化为0，每次得到合法区域的海拔和后，通过max函数更新ans，确保其始终保存当前最大的合法区域海拔和。
#include<bits/stdc++.h>// 引入C++所有标准库头文件，简化编码流程usingnamespacestd;intm,n,h;// 全局变量：地形图行数m、列数n、高度差阈值hinta[1005][1005];// 存储海拔高度的二维数组，1005×1005满足m、n≤10³的要求intans=0;// 存储最大合法3×3区域海拔和，初始化为0// 校验函数：判断以(x,y)为左上角的3×3区域是否合法// 合法条件：区域内最大海拔与最小海拔差值≤hboolcheck(intx,inty){intmx=a[x][y],mn=a[x][y];// 初始化最大/最小海拔为区域左上角值// 双层循环遍历3×3区域内所有9个点for(inti=x;i<x+3;i++){for(intj=y;j<y+3;j++){mx=max(mx,a[i][j]);// 更新区域最大海拔mn=min(mn,a[i][j]);// 更新区域最小海拔}}returnmx-mn<=h;// 返回区域是否合法的判断结果}// 求和函数：计算以(x,y)为左上角的3×3区域海拔总和intsum(intx,inty){intret=0;// 累加变量，存储区域海拔总和// 双层循环遍历3×3区域，累加所有点的海拔for(inti=x;i<x+3;i++){for(intj=y;j<y+3;j++){ret+=a[i][j];}}returnret;// 返回区域海拔总和}intmain(){// 输入行数m、列数n、高度差阈值hcin>>m>>n>>h;// 输入m行n列的海拔数据，采用1-based索引存储for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){cin>>a[i][j];}}// 修正后的循环条件：i≤m-2，j≤n-2，避免3×3区域越界for(inti=1;i<=m-2;i++){// i的有效上限为m-2，保证i+2≤mfor(intj=1;j<=n-2;j++){// j的有效上限为n-2，保证j+2≤n// 仅合法区域才计算海拔和并更新最大值if(check(i,j)){ans=max(ans,sum(i,j));}}}cout<<ans;// 输出最大合法区域海拔和return0;}
