一、题目大意 给定一个 NNN 行 MMM 列的整数矩阵（1<N,M≤700）（1 <N,M ≤ 700）（1<N,M≤700），每个元素表示对应位置的高度。需要统计矩阵中 “山顶” 的数量，山顶的定义如下： * 连通块：由一个或多个高度相同的格子组成，且格子间为八连通（上下左右 + 四个对角相邻）； * 山顶条件：该连通块中任意一个格子的八个相邻格子，要么超出矩阵边界，要么高度严格小于该连通块的高度。 简单来说，山顶是 “被更低的格子 / 边界完全包围的、高度相同的八连通块”，每个这样的连通块计为一个守卫（一个山顶）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、解题思路 核心思想 采用 "从高到低遍历 + 标记连通块 + 验证山顶条件” 的策略，规避 unordered_set 后，通过 “遍历矩阵找最大 / 最小高度 + 枚举高度” 实现，具体逻辑如下： * 确定高度范围：遍历矩阵找到所有高度的最小值和最大值，避免使用哈希集合存储不同高度； * 从高到低枚举高度：从最大值到最小值依次枚举每个可能的高度值（优先处理高海拔区域，避免低海拔区域干扰高海拔判断）； * 标记访问：维护一个访问矩阵，标记已处理过的格子，避免重复判断； * 连通块查找：对每个枚举的高度值，遍历矩阵找到所有未访问且高度等于当前值的格子，通过 BFS 找出其八连通的完整连通块； * 山顶验证：对每个连通块，检查其所有格子的八个相邻方向： 1.若存在任意一个相邻格子高度 ≥\geq≥ 当前连通块高度 → 该连通块不是山顶； 2.若所有相邻格子均为 “边界” 或 “高度严格更小” → 该连通块是山顶，计数 + 1； * 标记已处理：验证完成后，将该连通块的所有格子标记为已访问（后续不再处理）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、关键逻辑 * 八连通遍历：需枚举每个格子的 8 个方向（dx, dy），方向数组定义为 * 从高到低枚举高度：高海拔区域的山顶不会被低海拔区域影响，先处理高海拔可避免 “低海拔连通块误判高海拔区域” 的问题； * 避免重复处理：访问矩阵标记已处理的格子，确保每个格子仅被检查一次； * 无哈希集合的高度枚举：通过遍历矩阵获取最大 / 最小高度，再逐一枚举区间内的所有值，虽会枚举无对应格子的高度，但此类高度无连通块，不影响结果且时间可接受 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、注意点 * 八连通的正确性：必须枚举 8 个方向，而非 4 个（仅上下左右会漏判对角相邻的格子）； * 高度枚举的范围：需准确遍历 [min_h, max_h] 区间，避免遗漏可能的高度值； * 时间复杂度优化： 1.N、MN、MN、M 最大为 700700700，矩阵总元素为 490000490000490000，BFS 遍历每个元素仅一次，时间复杂度为 O(N∗M+(maxh−minh)NM)O (N*M + (max_h-min_h)NM)O(N∗M+(maxh −minh )NM)； 2.高度范围为 0 100000~100000 10000，最坏情况下枚举 100011000110001 次，总操作数约 4.9e94.9e94.9e9？实际优化：大部分高度无对应格子，内层循环会快速跳过，且 1s 可处理约 1e8 次操作，结合输入输出优化可通过； * 输入输出优化：必须使用; 否则 700x700 的矩阵输入会超时； * 边界判断：验证相邻格子时，需先判断是否超出矩阵范围（超出则视为 “合法边界”，无需检查高度）； * 避免重复处理：BFS 过程中立即标记格子为已访问，防止同一连通块被多次处理； * 山顶验证逻辑：仅需判断相邻格子是否 “严格更高”，等于当前高度的格子已被归入同一连通块（已标记为访问），无需额外处理。 六、后记 * 算法选择 1.采用 BFS 而非 DFS 的原因：DFS 递归处理 700x700 矩阵可能触发栈溢出，BFS 用队列实现更安全；若使用 DFS，需改为非递归实现（手动模拟栈）； 2.规避 unordered_set 后，通过 “枚举高度区间” 替代 “存储不同高度”，虽多枚举了无对应格子的高度，但实现简单且符合题目要求。 七、常见错误 * 漏判对角方向的相邻格子（仅用 4 连通）； * 未按从高到低遍历，导致低海拔连通块误判高海拔区域； * 验证山顶时，误将 “高度等于当前值” 的相邻格子视为 “非法”（实际此类格子已被归入同一连通块，验证时不会触发）； * 未标记已访问的格子，导致重复处理同一连通块； * 高度枚举范围错误（如未正确获取 max_h/min_h），导致遗漏部分高度的连通块。

#include <bits/stdc++.h> using namespace std; typedef pair<long long , long long> PII; long long dir[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); }