P3456 [POI2007] GRZ-Ridges and Valleys BFS-连通块思想

题目描述

Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity.

Therefore, in order to plan the journey and know how long it will last, he must know the number of ridgesand valleys in the area he is going to visit. And you are to help Byteasar.

Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape ofa n×nn×n square. For each field (i,j)(i,j) belonging to the square(for i,j∈{1,⋯ ,n}i,j∈{1,⋯,n}), its height w(i,j)w(i,j)​ is given.

We say two fields are adjacent if they have a common side or a common vertex (i.e. the field (i,j)(i,j) is adjacent to the fields (i−1,j−1)(i−1,j−1),(i−1,j)(i−1,j),(i−1,j+1)(i−1,j+1),(i,j−1)(i,j−1),(i,j+1)(i,j+1),(i+1,j−1)(i+1,j−1),(i+1,j)(i+1,j),(i+1,j+1)(i+1,j+1), provided that these fields are on the map).

We say a set of fields SS forms a ridge (valley) if:

all the fields in SS have the same height,the set SS forms a connected part of the map (i.e. from any field in SS it is possible to reach any other field in SS while moving only between adjacent fields and without leaving the set SS),if s∈Ss∈S and the field s′∉Ss′∈/S is adjacent to ss, then ws>ws′ws​>ws′​(for a ridge) or ws<ws′ws​<ws′​ (for a valley).

In particular, if all the fields on the map have the same height, they form both a ridge and a valley.

Your task is to determine the number of ridges and valleys for the landscape described by the map.

TaskWrite a programme that:

reads from the standard input the description of the map, determines the number of ridges and valleys for the landscape described by this map, writes out the outcome to the standard output.

给定一张地势图，求山峰和山谷的数量

输入格式

In the first line of the standard input there is one integer nn (2≤n≤1 0002≤n≤1 000)denoting the size of the map. Ineach of the following nn lines there is the description of the successive row of the map. In (i+1)(i+1)'th line(for i∈{1,⋯ ,n}i∈{1,⋯,n}) there are nn integers w(i,1),⋯ ,w(i,n)w(i,1)​,⋯,w(i,n)​(0≤wi≤1 000 000 0000≤wi​≤1 000 000 000), separated by single spaces. Thesedenote the heights of the successive fields of the ii'th row of the map.

输出格式

The first and only line of the standard output should contain two integers separated by a single space -thenumber of ridges followed by the number of valleys for the landscape described by the map.

题意翻译

题目描述

译自 POI 2007 Stage 2. Day 0「Ridges and Valleys」

给定一个 n×n 的网格状地图，每个方格 (i,j)(i,j) 有一个高度 wij。如果两个方格有公共顶点，则它们是相邻的。

定义山峰和山谷如下：

• 均由地图上的一个连通块组成；
• 所有方格高度都相同；
• 周围的方格（即不属于山峰或山谷但与山峰或山谷相邻的格子）高度均大于山谷的高度，或小于山峰的高度。

求地图内山峰和山谷的数量。特别地，如果整个地图方格的高度均相同，则整个地图既是一个山谷，也是一个山峰。

输入格式

第一行一个整数 n （2≤n≤1000），表示地图的大小。

接下来 n 行每行 n 个整数表示地图。第 ii行有 n 个整数 wi1,wi2,…,win(0≤wij≤1 000 000 000)，表示地图第 ii 行格子的高度。

输出格式

输出一行两个整数，分别表示山峰和山谷的数量。

样例解释

翻译来自于 LibreOJ。

输入输出样例

输入 #1复制

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

输出 #1复制

2 1

输入 #2复制

5
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

输出 #2复制

3 3

#include<iostream>
#include<cstring>
#include<algorithm>#define x first
#define y secondusing namespace std;typedef pair<int,int> PII;
const int N =1000+100;
int h[N][N]; 
bool cnt[N][N];
PII q[N*N];int n;/*** @brief 广度优先搜索 (BFS) 函数，用于遍历矩阵中的相邻元素。* * 该函数从给定的起始坐标 (x, y) 开始，检查其周围的 8 个相邻位置，* 判断是否存在比当前高度更高的点或更低的点，并更新 has_higher 和 has_lower 标志。* 如果存在相同高度的未访问点，则继续扩展搜索。* * @param x 起始坐标的行索引* @param y 起始坐标的列索引* @param has_higher 是否存在比当前高度更高的点* @param has_lower 是否存在比当前高度更低的点*/
void bfs(int x, int y, bool &has_higher, bool &has_lower)
{int hh = 0, tt = 0;q[0] = {x, y};cnt[x][y] = true;// BFS 遍历队列中的所有节点while (hh <= tt){PII t = q[hh++];// 遍历当前节点的 8 个相邻位置for (int i = t.x - 1; i <= t.x + 1; i++){for (int j = t.y - 1; j <= t.y + 1; j++){// 检查边界条件，防止越界if (i < 0 || j < 0 || i >= n || j >= n) continue;// 如果相邻点的高度不同，更新 has_higher 和 has_lower 标志if (h[i][j] != h[t.x][t.y]){if (h[i][j] > h[t.x][t.y]) has_higher = true;else if (h[i][j] < h[t.x][t.y]) has_lower = true;}// 如果相邻点的高度相同且未访问过，加入队列继续搜索else if (!cnt[i][j]){cnt[i][j] = true;q[++tt] = {i, j};}}}}
}int main()
{// 输入矩阵大小 nscanf("%d", &n);// 输入矩阵 h 的值for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){scanf("%d", &h[i][j]);}}int peak = 0;int val = 0;// 遍历矩阵中的每个点，使用 BFS 判断是否为山顶或山谷for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (!cnt[i][j]){bool has_higher = false, has_lower = false;bfs(i, j, has_higher, has_lower);// 如果没有更高的点，则为山顶if (!has_higher) peak++;// 如果没有更低的点，则为山谷if (!has_lower) val++;}}}// 输出山顶和山谷的数量cout << peak << " " << val << endl;return 0;
}