B4451 [GESP202512 四级] 建造

题目描述

小 A 有一张 $M$ 行 $N$ 列的地形图，其中第 $i$ 行第 $j$ 列的数字 $a_{ij}$ 代表坐标 $(i,j)$ 的海拔高度。

停机坪为一个 $3\times 3$ 的区域，且内部所有 $9$ 个点的最大高度和最小高度之差不超过 $H$。

小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部 $9$ 个点海拔之和最大是多少。

输入格式

第一行三个正整数 $M,N,H$，含义如题面所示。

之后 $M$ 行，第 $i$ 行包含 $N$ 个整数 $a_{i1},a_{i2},\dots ,a_{iN}$，代表坐标 $(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\le M,N\le 10^3$，$1\le H,a_{ij}\le 10^5$。

题解：建造

一、 解题思路

1. 确定遍历对象：3×3区域的位置由其左上角坐标(i,j)唯一确定，有效左上角坐标的行范围是1~m-2、列范围是1~n-2（该范围可保证3×3区域不超出地形图边界），遍历该范围内所有坐标即可覆盖所有潜在停机坪区域。
2. 合法性校验：对每个左上角(i,j)对应的3×3区域，遍历区域内9个点，找出最大海拔和最小海拔，判断两者差值是否不超过阈值H，满足条件则该区域合法。
3. 计算海拔总和：对于合法的3×3区域，再次遍历区域内9个点，累加所有点的海拔高度，得到该区域的海拔总和。
4. 维护全局最大值：定义全局变量ans存储最终结果并初始化为0，每次得到合法区域的海拔和后，通过max函数更新ans，确保其始终保存当前最大的合法区域海拔和。

#include <bits/stdc++.h>  // 引入C++所有标准库头文件，简化编码流程
using namespace std;

int m,n,h;  // 全局变量：地形图行数m、列数n、高度差阈值h
int a[1005][1005];  // 存储海拔高度的二维数组，1005×1005满足m、n≤10³的要求
int ans=0;  // 存储最大合法3×3区域海拔和，初始化为0

// 校验函数：判断以(x,y)为左上角的3×3区域是否合法
// 合法条件：区域内最大海拔与最小海拔差值≤h
bool check(int x,int y){
    int mx=a[x][y],mn=a[x][y];  // 初始化最大/最小海拔为区域左上角值
    // 双层循环遍历3×3区域内所有9个点
    for(int i=x;i<x+3;i++){
        for(int j=y;j<y+3;j++){
            mx=max(mx,a[i][j]);  // 更新区域最大海拔
            mn=min(mn,a[i][j]);  // 更新区域最小海拔
        }
    }
    return mx-mn<=h;  // 返回区域是否合法的判断结果
}

// 求和函数：计算以(x,y)为左上角的3×3区域海拔总和
int sum(int x,int y){
    int ret=0;  // 累加变量，存储区域海拔总和
    // 双层循环遍历3×3区域，累加所有点的海拔
    for(int i=x;i<x+3;i++){
        for(int j=y;j<y+3;j++){
            ret+=a[i][j];
        }
    }
    return ret;  // 返回区域海拔总和
}

int main() {
    // 输入行数m、列数n、高度差阈值h
    cin>>m>>n>>h;
    // 输入m行n列的海拔数据，采用1-based索引存储
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    // 修正后的循环条件：i≤m-2，j≤n-2，避免3×3区域越界
    for(int i=1;i<=m-2;i++){  // i的有效上限为m-2，保证i+2≤m
        for(int j=1;j<=n-2;j++){  // j的有效上限为n-2，保证j+2≤n
            // 仅合法区域才计算海拔和并更新最大值
            if (check(i,j)){
                ans=max(ans,sum(i,j));
            }
        }
    }
    cout<<ans;  // 输出最大合法区域海拔和
    return 0;
}