题解

#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;

}