问题分析

我们需要在一个 $n \times n$ 的网格中统计山峰和山谷的数量：

• 山峰：一个连通区域，所有格子高度相同，且周围相邻格子高度都小于该区域
• 山谷：一个连通区域，所有格子高度相同，且周围相邻格子高度都大于该区域
• 特殊情况：如果整个地图高度相同，则它既是山峰也是山谷

算法思路

核心思想：BFS连通块分析

对每个未访问的格子，进行BFS遍历找到所有高度相同的连通区域，同时检查该区域周围格子的高度关系：

• 如果周围有更高的格子，则不可能是山峰
• 如果周围有更低的格子，则不可能是山谷

关键变量

• has_h：标记连通块周围是否存在更高格子
• has_l：标记连通块周围是否存在更低格子

代码详细解析

1. 数据定义和方向数组

int w[N][N];        // 存储网格高度
bool st[N][N];      // 标记是否访问过
int dx[] = {0,0,1,1,1,-1,-1,-1};  // 8方向移动
int dy[] = {1,-1,0,1,-1,0,1,-1};

8方向移动对应题目中的"有公共顶点就算相邻"。

2. BFS遍历函数

void bfs(int sx, int sy, bool &has_h, bool &has_l) {
    queue<pii> q;
    q.push({sx, sy});
    st[sx][sy] = true;
    int h = w[sx][sy];  // 当前连通块的高度

    while (!q.empty()) {
        int x = q.front().xx;
        int y = q.front().yy;
        q.pop();

        for (int k = 0; k < 8; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;
            
            if (w[nx][ny] == h && !st[nx][ny]) {
                // 相同高度，加入连通块
                st[nx][ny] = true;
                q.push({nx, ny});
            } else if (w[nx][ny] != h) {
                // 不同高度，更新边界信息
                if (w[nx][ny] > h) has_h = true;
                if (w[nx][ny] < h) has_l = true;
            }
        }
    }
}

3. 主逻辑流程

特殊情况检查

bool all_s = true;
for (int i = 0; i < n && all_s == true; ++i) {
    for (int j = 0; j < n && all_s == true; ++j) {
        if (w[i][j] != w[0][0])
            all_s = false;
    }
}
if (all_s) {
    cout << 1 << " " << 1;  // 整个地图既是山峰也是山谷
    return 0;
}

遍历所有连通块

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        if (!st[i][j]) {
            bool has_h = false, has_l = false;
            bfs(i, j, has_h, has_l);
            
            // 山峰：周围没有更高，但有更低的格子
            if (has_l && !has_h) cntp++;
            // 山谷：周围没有更低，但有更高的格子  
            if (has_h && !has_l) cntv++;
        }
    }
}

算法正确性分析

为什么这样能正确统计？

1. 连通性保证：BFS确保找到完整的连通区域
2. 边界检查：在遍历时检查所有8方向的邻居
3. 逻辑判断：
   • 山峰：必须存在更低邻居(has_l=true)且不能有更高邻居(has_h=false)
   • 山谷：必须存在更高邻居(has_h=true)且不能有更低邻居(has_l=false)

边界情况处理

• 平坦区域：如果!has_l && !has_h，说明是内部区域，不计入
• 混合边界：如果has_l && has_h，说明是斜坡，不计入

复杂度分析

• 时间复杂度：$O(n^2)$
  • 每个格子最多被访问一次
  • 每个格子的8个邻居最多被检查一次
• 空间复杂度：$O(n^2)$
  • 存储网格和访问标记

样例验证

样例1

8 8 8 7 7
7 7 8 8 7  
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

输出：2 1 ✓

样例2

5 7 8 3 1
5 5 7 6 6
6 6 6 2 8  
5 7 2 5 8
7 1 0 1 7

输出：3 3 ✓

总结

本题通过BFS遍历连通区域，并在遍历过程中收集边界信息，从而判断每个连通区域是山峰、山谷还是普通区域。算法简洁高效，正确处理了所有边界情况。