「一本通 1.4 练习 4」山峰和山谷

题目描述

给定 $n\times n$ 的网格，每格有高度 $w_{ij}$ ，有公共顶点即相邻（8 邻接）。等高的 8 连通块，若周围格子都比它矮则为山峰，都比它高则为山谷；全图同高时整体既算山峰也算山谷。求山峰与山谷的数量。

输入：第一行 $n$ （ $2\le n\le1000$ ），随后 $n$ 行每行 $n$ 个整数 $w_{ij}$ （ $0\le w_{ij}\le10^9$ ）。输出：一行两个整数，山峰数与山谷数。样例：输入 5 / 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。

思路

枚举每个未访问的格子，用 BFS 沿 8 个方向吞并所有同高的格子，得到一个等权连通块。洪泛时检查块内每格的 8 个邻居：出界忽略，同高则并入，更高或更矮分别记录 has_higher / has_lower；块外邻居必与块高不同，所以无更高即山峰、无更矮即山谷，两者可同时成立，全图同高的特例自然被覆盖。总复杂度 $O(n^2)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 11:45
# update_at: 2026-09-30 11:45

import sys
from collections import deque

# 8 邻接方向：题面把「有公共顶点」也算相邻，所以含 4 条对角线
DIRS = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))


def explore(grid: list[list[int]], seen: list[bytearray], start: tuple[int, int]) -> tuple[bool, bool]:
    """从 start 洪泛一个「高度全相同且 8 连通」的块。

    返回值是 (是否山峰, 是否山谷)：山峰要求周围都比它矮，山谷要求周围都比它高，
    所以「有比它高的」就不可能是山峰，「有比它矮的」就不可能是山谷。
    整个地图高度相同时两侧都不会被排除，两种身份同时成立。
    """
    n = len(grid)
    height = grid[start[0]][start[1]]
    has_lower = has_higher = False
    queue = deque([start])
    seen[start[0]][start[1]] = 1

    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < n and 0 <= nc < n):  # 出界：不是格子，不参与比较
                continue
            if grid[nr][nc] == height:
                if not seen[nr][nc]:               # 同高且未访问：并入当前块
                    seen[nr][nc] = 1
                    queue.append((nr, nc))
            elif grid[nr][nc] < height:            # 块外邻居：定身份用，不入队
                has_lower = True
            else:
                has_higher = True

    return not has_higher, not has_lower


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    grid = [[next(data) for _ in range(n)] for _ in range(n)]

    seen = [bytearray(n) for _ in range(n)]  # seen[r][c]=1 表示该格已被归入某个块
    peaks = valleys = 0

    for r in range(n):
        for c in range(n):
            if not seen[r][c]:
                is_peak, is_valley = explore(grid, seen, (r, c))
                peaks += is_peak                 # bool 相加等价于 if ... : ans += 1
                valleys += is_valley

    print(peaks, valleys)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:55
 * update_at: 2026-10-05 23:55
 */
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

typedef long long ll;

const int MAXN = 1005;

int n;
int grid[MAXN][MAXN];   // grid[i][j] 表示格子 (i, j) 的高度
char seen[MAXN][MAXN];  // seen[i][j] = 1 表示该格已被归入某个等权连通块

// 8 邻接方向：题面把「有公共顶点」也算相邻，所以含 4 条对角线
const int DIRR[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int DIRC[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 从 (sr, sc) 洪泛一个高度全相同且 8 连通的块。
// is_peak 记录是否山峰（无更高的外部邻居），is_valley 记录是否山谷（无更矮的外部邻居）。
void bfs_block(int sr, int sc, bool &is_peak, bool &is_valley) {
    int height = grid[sr][sc];
    bool has_higher = false;  // 块外存在更高的邻居
    bool has_lower = false;   // 块外存在更矮的邻居

    queue<pair<int, int> > q;
    q.push(make_pair(sr, sc));
    seen[sr][sc] = 1;

    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        for (int d = 0; d < 8; d++) {
            int nr = r + DIRR[d];
            int nc = c + DIRC[d];
            if (nr < 1 || nr > n || nc < 1 || nc > n) {
                continue;  // 出界：边界外不是格子，不参与比较
            }
            if (grid[nr][nc] == height) {
                if (!seen[nr][nc]) {  // 同高且未访问：并入当前块
                    seen[nr][nc] = 1;
                    q.push(make_pair(nr, nc));
                }
            } else if (grid[nr][nc] > height) {
                has_higher = true;
            } else {
                has_lower = true;
            }
        }
    }

    is_peak = !has_higher;
    is_valley = !has_lower;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> grid[i][j];
        }
    }

    ll peaks = 0;
    ll valleys = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (!seen[i][j]) {
                bool is_peak = false;
                bool is_valley = false;
                bfs_block(i, j, is_peak, is_valley);
                if (is_peak) {
                    peaks++;
                }
                if (is_valley) {
                    valleys++;
                }
            }
        }
    }

    cout << peaks << " " << valleys << "\n";
    return 0;
}

「一本通 1.4 练习 4」山峰和山谷

目录

题目描述

思路

参考代码