AcWing算法提高课-2.1.3山峰和山谷

题目描述

FGD 小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排，他想知道山峰和山谷的数量。

给定一个地图，为 FGD 想要旅行的区域，地图被分为 $\times n$ 的网格，每个格子 $(i, j)$ 的高度 $w_{i,j}$ 是给定的。

若两个格子有公共顶点，那么它们就是相邻的格子，如与 $(i, j)$ 相邻的格子有 $(i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1)$ 。

我们定义一个格子的集合 $S$ 为山峰（山谷）当且仅当：

$S$ 的所有格子都有相同的高度。
$S$ 的所有格子都连通。
对于 $s\in S$ ，与 $s$ 相邻的 $s’\notin S$ ，都有 $w_s > w_{s’}$ （山峰），或者 $w_s < w_{s’}$ （山谷）。
如果周围不存在相邻区域，则同时将其视为山峰和山谷。

你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入格式

第一行包含一个正整数 $n$ ，表示地图的大小。

接下来一个 $\times n$ 的矩阵，表示地图上每个格子的高度 $w$ 。

输出格式

共一行，包含两个整数，表示山峰和山谷的数量。

数据范围

$\le n \le 1000$ ,
$\le w \le 10^9$

思路

发现对于每个连通块

四周没有比他高的，他就是山峰；
四周没有比他低的，他就是山谷；
如果都有，那么他啥也不是。

因此考虑 BFS 搜索连通块。

如果一个连通块周围没有比他高的，那他就是山峰。同理判断山谷。

算法时间复杂度 $O(n^2)$

`AC Code`

$\text{C}++$

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1010;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0}; // 8方向偏移量
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n;
int h[N][N];
queue<PII> q;
bool st[N][N];

void bfs(int x, int y, bool& f1, bool& f2)
{
    q.push({x, y}); // 起点入队
    st[x][y] = 1; // 起点被遍历过

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 8; i ++ ) // 8方向扩展
        {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue; // 如果出界就继续
            if (h[xx][yy] != h[t.x][t.y]) // 如果扩展出的和现在的高度不相等
            {
                if (h[xx][yy] > h[t.x][t.y]) f1 = 1; // 高的话是山峰
                else f2 = 1; // 否则是山谷
            }
            else if (!st[xx][yy]) // 如果没被遍历过
            {
                st[xx][yy] = 1;
                q.push({xx, yy}); // 入队
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &h[i][j]);

    int r1 = 0, r2 = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (!st[i][j]) // 遍历整个图
            {
                bool f1 = 0, f2 = 0;
                bfs(i, j, f1, f2);
                if (!f1) r1 ++ ; // 山峰
                if (!f2) r2 ++ ; // 山谷
            }

    printf("%d %d\n", r1, r2);
    return 0;
}