[BFS题解] A91482

一、题目大意

给定一个 $N$ 行 $M$ 列的整数矩阵$（1 <N,M ≤ 700）$，每个元素表示对应位置的高度。需要统计矩阵中 “山顶” 的数量，山顶的定义如下：

• 连通块：由一个或多个高度相同的格子组成，且格子间为八连通（上下左右 + 四个对角相邻）；
• 山顶条件：该连通块中任意一个格子的八个相邻格子，要么超出矩阵边界，要么高度严格小于该连通块的高度。

简单来说，山顶是 “被更低的格子 / 边界完全包围的、高度相同的八连通块”，每个这样的连通块计为一个守卫（一个山顶）。

---

二、解题思路

核心思想

采用 "从高到低遍历 + 标记连通块 + 验证山顶条件” 的策略，规避 unordered_set 后，通过 “遍历矩阵找最大 / 最小高度 + 枚举高度” 实现，具体逻辑如下：

• 确定高度范围：遍历矩阵找到所有高度的最小值和最大值，避免使用哈希集合存储不同高度；

• 从高到低枚举高度：从最大值到最小值依次枚举每个可能的高度值（优先处理高海拔区域，避免低海拔区域干扰高海拔判断）；

• 标记访问：维护一个访问矩阵，标记已处理过的格子，避免重复判断；

• 连通块查找：对每个枚举的高度值，遍历矩阵找到所有未访问且高度等于当前值的格子，通过 BFS 找出其八连通的完整连通块；

• 山顶验证：对每个连通块，检查其所有格子的八个相邻方向：
  1.若存在任意一个相邻格子高度 $\geq$ 当前连通块高度 → 该连通块不是山顶；
  2.若所有相邻格子均为 “边界” 或 “高度严格更小” → 该连通块是山顶，计数 + 1；

• 标记已处理：验证完成后，将该连通块的所有格子标记为已访问（后续不再处理）。

---

三、关键逻辑

• 八连通遍历：需枚举每个格子的 8 个方向（dx, dy），方向数组定义为

int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}；

• 从高到低枚举高度：高海拔区域的山顶不会被低海拔区域影响，先处理高海拔可避免 “低海拔连通块误判高海拔区域” 的问题；
• 避免重复处理：访问矩阵标记已处理的格子，确保每个格子仅被检查一次；
• 无哈希集合的高度枚举：通过遍历矩阵获取最大 / 最小高度，再逐一枚举区间内的所有值，虽会枚举无对应格子的高度，但此类高度无连通块，不影响结果且时间可接受

---

四、代码

#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);
    
    long long N , M;
    cin >> N >> M;
    vector<vector<int>> grid(N, vector<int>(M));
    long long min_h = 10001;
    long long max_h = -1; // 高度范围0~10000，初始化边界值
    
    // 读入矩阵并确定高度的最大/最小值
    for (int i = 0 ; i < N ; i++) {
        for (int j = 0 ; j < M ; j++) {
            cin >> grid[i][j];
            if (grid[i][j] > max_h) {
                max_h = grid[i][j];
            }
            if (grid[i][j] < min_h) {
                min_h = grid[i][j];
            }
        }
    }
    
    vector<vector<bool>> visited(N , vector<bool>(M , false));
    long long ans = 0; // 山顶数量
    
    // 从高到低枚举所有可能的高度
    for (int h = max_h ; h >= min_h ; h--) {
        // 遍历所有未访问且高度为h的格子
        for (int i = 0 ; i < N ; i++) {
            for (int j = 0 ; j < M ; j++) {
                if (grid[i][j] == h && !visited[i][j]) {
                    // BFS找八连通块
                    queue<PII> q;
                    vector<PII> block; // 存储当前连通块的所有格子
                    q.push({i, j});
                    visited[i][j] = true;
                    block.push_back({i, j});
                    
                    while (!q.empty()) {
                        auto [x, y] = q.front();
                        q.pop();
                        for (int d = 0 ; d < 8 ; d++) {
                            long long nx = x + dir[d][0];
                            long long ny = y + dir[d][1];
                            // 边界判断 + 高度相等 + 未访问
                            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                                if (grid[nx][ny] == h && !visited[nx][ny]) {
                                    visited[nx][ny] = true;
                                    q.push({nx, ny});
                                    block.push_back({nx, ny});
                                }
                            }
                        }
                    }
                    
                    // 验证是否为山顶
                    bool is_peak = true;
                    for (auto [x, y] : block) {
                        for (int d = 0; d < 8; d++) {
                            int nx = x + dir[d][0];
                            int ny = y + dir[d][1];
                            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                                // 存在更高的相邻格子，不是山顶
                                if (grid[nx][ny] > h) {
                                    is_peak = false;
                                    break;
                                }
                            }
                        }
                        if (!is_peak) {
                            break;
                        }
                    }
                    
                    if (is_peak) {
                        ans++;
                    }
                }
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

---

五、注意点

• 八连通的正确性：必须枚举 8 个方向，而非 4 个（仅上下左右会漏判对角相邻的格子）；
• 高度枚举的范围：需准确遍历 [min_h, max_h] 区间，避免遗漏可能的高度值；
• 时间复杂度优化：
  1.$N、M$ 最大为 $700$，矩阵总元素为 $490000$，BFS 遍历每个元素仅一次，时间复杂度为 $O (N*M + (max_h-min_h)NM)$；
  2.高度范围为 $0~10000$，最坏情况下枚举 $10001$ 次，总操作数约 $4.9e9$？实际优化：大部分高度无对应格子，内层循环会快速跳过，且 1s 可处理约 1e8 次操作，结合输入输出优化可通过；
• 输入输出优化：必须使用;

 ios::sync_with_stdio(false); cin.tie(nullptr)

否则 700x700 的矩阵输入会超时；

• 边界判断：验证相邻格子时，需先判断是否超出矩阵范围（超出则视为 “合法边界”，无需检查高度）；
• 避免重复处理：BFS 过程中立即标记格子为已访问，防止同一连通块被多次处理；
• 山顶验证逻辑：仅需判断相邻格子是否 “严格更高”，等于当前高度的格子已被归入同一连通块（已标记为访问），无需额外处理。

六、后记

• 算法选择
  1.采用 BFS 而非 DFS 的原因：DFS 递归处理 700x700 矩阵可能触发栈溢出，BFS 用队列实现更安全；若使用 DFS，需改为非递归实现（手动模拟栈）；
  2.规避 unordered_set 后，通过 “枚举高度区间” 替代 “存储不同高度”，虽多枚举了无对应格子的高度，但实现简单且符合题目要求。

七、常见错误

• 漏判对角方向的相邻格子（仅用 4 连通）；
• 未按从高到低遍历，导致低海拔连通块误判高海拔区域；
• 验证山顶时，误将 “高度等于当前值” 的相邻格子视为 “非法”（实际此类格子已被归入同一连通块，验证时不会触发）；
• 未标记已访问的格子，导致重复处理同一连通块；
• 高度枚举范围错误（如未正确获取 max_h/min_h），导致遗漏部分高度的连通块。