山峰和山谷

FloodFill BFS

题目描述

译自 POI 2007 Stage 2. Day 0「Ridges and Valleys」 #2653. 「POI2007」山峰和山谷 Ridges and Valleys - 题目 - LibreOJ (loj.ac) 给定一个 $n\times n$ 的网格状地图，每个方格 $(i,j)$ 有一个高度 $w_{ij}$。如果两个方格有公共顶点，则它们是相邻的。

定义山峰和山谷如下：

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

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

输入格式

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

接下来 $n$ 行每行 $n$ 个整数表示地图。第 $i$ 行有 $n$ 个整数 $w_{i1},w_{i2},\dots ,w_{in}(0\le w_{ij}\le 1000000000)$，表示地图第 $i$ 行格子的高度。

输出格式

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

样例 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

输出

2 1

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

输出

3 3

1

思路

依然是一个点周围8个点都算连通, 这里需要找山峰的数量和山谷的数量。 山峰是指该点的权值大于周围点的权值的连通点集是一个山峰。 山谷同理, 是该点权值小于周围点权值的连通点集是一个山谷。

同样声明st数组记录当前点是否被枚举过, 先循环遍历所有点, 遇到未枚举过的点就进行BFS泛洪标记与当前值相同的连通点集, 并判断点集周围是否存在大于的点或者小于的点。

如果周围不存在小于当前权值的点, 说明当前点集为山谷。 若周围不存在大于当前取值的点, 说明当前点集为山峰。

若既不存在大于也不存在小于, 说明该图权值都相等, 即是山谷也是山峰。

代码

const int N = 1e3 + 10;
int g[N][N];
int n;
bool st[N][N];
int res_u, res_n; // 山谷与山峰
typedef pair<int, int> PII;
PII q[N * N];
 
void bfs(int xx, int yy, bool &highter, bool &lower)
{
    int hh = 0, tt = 0;
    q[0] = {xx, yy};
    st[xx][yy] = true;
    while (hh <= tt)
    {
        auto t = q[hh++];
        for (int i = t.first - 1; i <= t.first + 1; i++)
            for (int j = t.second - 1; j <= t.second + 1; j++)
            {
                if (i < 1 || i > n || j < 1 || j > n)
                    continue;
                if (g[i][j] != g[t.first][t.second])
                {
                    if (g[i][j] > g[t.first][t.second])
                        highter = true;
                    else
                        lower = true;
                }
                else if (!st[i][j])
                {
                    q[++tt] = {i, j};
                    st[i][j] = true;
                }
            }
    }
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (st[i][j])
                continue;
            bool higher = false, lower = false;
            bfs(i, j, higher, lower);
            if (!higher)
                res_n++;
            if (!lower)
                res_u++;
        }
    cout << res_n << " " << res_u << endl;
 
    return 0;
}