PP4888 山峰和山谷（提高）

这道题要在 n×n 的地图里数出山峰和山谷各有多少个，关键是把"连通块"找清楚，再判断每个连通块四周的高低。n 最大到 1000，格子最多有一百万个，所以要用高效的搜索算法。

解题思路

第一步，理解连通块。 两个格子只要有公共顶点（上下左右和 4 个斜角，共 8 个方向）就算相邻。高度相同且通过这种相邻关系连在一起的一批格子，组成一个连通块。

第二步，理解山峰和山谷的判定。 一个连通块找出来之后，看它四周相邻的格子（高度和它不同的格子）：四周都比它高，它是山谷；四周都比它矮，它是山峰；四周既有比它高的又有比它矮的，它就什么也不是。特殊情况：如果整张地图所有格子高度都相同，那么整张图既是山峰又是山谷，答案输出 1 1。

第三步，用 BFS 找连通块。 从左上角开始，遇到没访问过的格子就启动一次 BFS：把它加入队列，然后不断从队头取出格子，把 8 个方向中高度相同且没访问过的格子加入队尾并标记，直到队列空，这个连通块就完整了。因为每个格子只入队一次，总时间是 O(n²)。

第四步，搜索时顺便记录高低。 BFS 扩展时，对 8 个方向的邻居逐个判断：和当前块高度相同，就入队；比当前块高，记下 up=1；比当前块矮，记下 dn=1。一个连通块结束后看 up 和 dn：up 为 1 且 dn 为 0，山谷数加 1；up 为 0 且 dn 为 1，山峰数加 1；up、dn 都是 0，说明全图同高，山峰、山谷各加 1。

第五步，看样例验证。 样例里有两个 8 的连通块，它们四周只有 7，所以各算一个山峰；7 的大连通块四周有 8，比它高，算一个山谷，最终输出 2 1。

第六步，注意性能与边界。 高度要开 int 数组（值可达 10 亿），访问标记用 char 省内存；队列数组要开够一百万个位置；判断邻居时先看是否越界。BFS 队列用两个数组分别存 x、y 坐标，配合头尾指针使用。

参考代码

// 统计地图中山峰和山谷的数量，8方向同高连通块
#include <iostream>
using namespace std;

int a[1005][1005]; // 高度地图
char v[1005][1005]; // 访问标记
int qx[1000005], qy[1000005]; // BFS队列存坐标
int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};
int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    int peak = 0, valley = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (v[i][j]) continue; // 已访问过
            int head = 0, tail = 0;
            qx[tail] = i; qy[tail] = j; tail++;
            v[i][j] = 1;
            int h = a[i][j];       // 本连通块高度
            int up = 0, dn = 0;    // 有更高/更低邻居
            while (head < tail) {
                int x = qx[head], y = qy[head]; head++;
                for (int d = 0; d < 8; d++) {
                    int nx = x + dx[d], ny = y + dy[d];
                    if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
                    if (a[nx][ny] == h) {
                        if (!v[nx][ny]) {
                            v[nx][ny] = 1;
                            qx[tail] = nx; qy[tail] = ny; tail++;
                        }
                    } else if (a[nx][ny] > h) up = 1;
                    else dn = 1;
                }
            }
            if (!up && !dn) { peak++; valley++; } // 全图同高，既山又谷
            else if (up && !dn) valley++;
            else if (!up && dn) peak++;
        }
    }
    cout << peak << " " << valley << endl;
    return 0;
}

复杂度分析

复杂度分析：每个格子恰好入队一次，每次判断 8 个方向是常数操作，所以 BFS 总时间 O(n²)；空间上高度数组、标记数组和队列都是 O(n²)。n=1000 时约一百万个格子，运行时间很短，可以轻松通过评测。