题目描述

https://www.acwing.com/problem/content/1108/

样例

输入样例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 <queue>
using namespace std;
const int N = 1010;
int dist[N][N];
int h[N][N];
int n;

void bfs(int x, int y, bool& has_higher, bool& has_lower)
{
    queue<pair<int,int>> q;
    q.push({x, y});
    dist[x][y] = 0;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = t.first - 1; i <= t.first + 1; i ++ )
            for (int j = t.second - 1; j <= t.second + 1; j ++ )
            {
                if (i == t.first && j == t.second) continue;
                if (i < 0 || i >= n || j < 0 || j >= n) continue;
                if (h[i][j] != h[t.first][t.second])//判断山脉边界
                {
                    if (h[i][j] > h[t.first][t.second]) has_higher = true;
                    else has_lower = true;
                }
                else if (dist[i][j] == -1)
                {
                    q.push({i, j});
                    dist[i][j] = dist[t.first][t.second] + 1;
                }
            }
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ ) scanf("%d", &h[i][j]);
    memset(dist, -1, sizeof(dist));
    int peak = 0, valley = 0;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
        {
            if (dist[i][j] == -1)
            {
                bool has_higher = false, has_lower = false;
                bfs(i, j, has_higher, has_lower);
                if (!has_higher) peak ++ ;
                if (!has_lower) valley ++ ;
            }
        }
    }
    printf("%d %d\n", peak, valley);
    return 0;
}