信息学奥赛一本通T1454-山峰和山谷（广度搜索）

解题思路:

根据题目描述

1、没有比它高的叫山峰

2、没有比它矮的叫山谷

3、还存在又比它高，又比它矮的不算山峰也不算山谷

步骤：

找到高度一致的连通块，若该连通块周围

        没有存在比它高的则该连通块叫山峰

        没有存在比它矮的则该连通块叫山谷

注意事项:

该代码实现了统计山峰和山谷的数量。

首先定义了一个二维数组w[N][N]，表示地形的高度。vis[N][N]数组用于标记是否访问过某个位置。

然后定义了一个队列q，用于进行广度优先搜索。

接下来的bfs函数用于进行广度优先搜索。它的参数x和y表示起始位置，has_higher和has_lower分别表示是否有更高和更低的地形。首先将起始位置加入队列，并将其标记为已访问。然后开始广度优先搜索，每次从队列中取出一个位置，遍历其周围的位置。如果周围的位置的高度与当前位置的高度不同，根据高度的大小更新has_higher和has_lower。如果周围的位置与当前位置的高度相同且未访问过，则将其加入队列并标记为已访问。最后，当队列为空时，搜索结束。

主函数中首先读入地形的高度。然后使用两层循环遍历每个位置，如果该位置未访问过，则调用bfs函数进行广度优先搜索，并根据has_higher和has_lower的值更新山峰和山谷的数量。

最后输出山峰和山谷的数量。

该代码的时间复杂度为O(n^2)，其中n为地形的大小。

参考代码:

#include <iostream>

#include <queue>

#define x first

#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, w[N][N], vis[N][N];

queue<PII> q;

void bfs(int x, int y, bool & has_higher, bool & has_lower)

{

    q.push({x, y});

    vis[x][y] = 1;

    while (!q.empty())

    {

        PII p = q.front();

        q.pop();

        for (int i = p.x - 1; i <= p.x + 1; i++)

            for (int j = p.y - 1; j <= p.y + 1; j++)

            {

                if (i == p.x && j == p.y) continue;

                if (i < 1 || i > n || j < 1 || j > n) continue;

                if (w[i][j] != w[p.x][p.y])

                {

                    if (w[i][j] > w[p.x][p.y]) has_higher = false; // 周围的高说明当前不是山峰 

                    else has_lower = false; // 周围的低说明当前不是山谷 

                }

                else if (!vis[i][j]) // 把相同高度的加入到队列 

                {

                    vis[i][j] = 1;

                    q.push({i, j});

                }

            }

    }

}

int main()

{

    cin >> n;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= n; j++)

            cin >> w[i][j];

    int peak = 0, valley = 0;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= n; j++)

            if (!vis[i][j])

            {

                bool has_higher = true, has_lower = true;

                bfs(i, j, has_higher, has_lower);

                if (has_higher) peak++;

                if (has_lower) valley++;

            }

    cout << peak << ' ' << valley << endl;

    return 0;

}