山峰和山谷

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1836 字
BFS 找同高连通块，比较周围格子高度
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1454
// 题意：n * n 网格每个格子有高度，同高度的连通块若周围格子都比它高则是山谷、都比它低则是山峰（全图同高时两者都算），求山峰和山谷的个数。
// 思路：BFS 求同高度连通块，再看块外邻居的高度关系。
// 1. 八个方向都算相邻，连通块用同高度扩散求出。
// 2. 扫描连通块的所有相邻格：出现更高的邻居就不是山峰，出现更低的邻居就不是山谷。
// 3. 两个条件都不成立时同时计数，正好覆盖全图同高的特例。
// 复杂度：O(n^2) 时间 / O(n^2) 空间
// 易错点：相邻是八连通（含对角），只查四方向会把对角上的高格子漏掉，导致多算山峰。
// 易错点：判断的是「连通块外部」的邻居，块内格子高度一定相同，不用参与比较。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    if(!(cin >> n)) return 0;
    vector<vector<long long>> a(n, vector<long long>(n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) cin >> a[i][j];
    }
    vector<vector<int>> vis(n, vector<int>(n, 0));
    int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    int peak = 0, valley = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(vis[i][j]) continue;
            queue<pair<int, int>> q;
            q.push({i, j});
            vis[i][j] = 1;
            bool higher = false, lower = false;
            while(!q.empty()){
                int r = q.front().first;
                int c = q.front().second;
                q.pop();
                for(int k = 0; k < 8; k++){
                    int nr = r + dr[k], nc = c + dc[k];
                    if(nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                    if(a[nr][nc] == a[i][j]){
                        if(!vis[nr][nc]){
                            vis[nr][nc] = 1;
                            q.push({nr, nc});
                        }
                    }
                    else if(a[nr][nc] > a[i][j]) higher = true;
                    else lower = true;
                }
            }
            if(!higher) peak++;
            if(!lower) valley++;
        }
    }
    cout << peak << " " << valley << "\n";
    return 0;
}
山峰和山谷

正文

一本通·提高篇的其它内容
