蓝桥集训之山峰和山谷

蓝桥集训之山峰和山谷

• 核心思想：Flood Fill

  • 多加两个bool变量 记录连通块周围是否有比它大/小的数

•   #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    typedef pair<int,int> PII;
    const int N = 1010,M = N*N;
    
    PII p[M];
    int h[N][N];
    bool st[N][N];
    int n;
    
    void bfs(int x,int y,bool &has_peak,bool &has_valley)
    {
        st[x][y] = true;
        p[0] = {x,y};
        int hh=0,tt=0;
        
        while(hh<=tt)
        {
            auto t = p[hh++];
            int a = t.first , b = t.second;
            for(int i=a-1;i<=a+1;i++)
            {
                for(int j=b-1;j<=b+1;j++)
                {
                    if (i < 0 || i >= n || j < 0 || j >= n) continue;
                    if(h[i][j] != h[a][b])
                    {
                        if(h[i][j] > h[a][b]) has_peak = true;
                        else has_valley = true;
                    }
                    else if(!st[i][j])
                    {
                        p[++tt] = {i,j};
                        st[i][j] = true;
                    }
                }
            }
        }
    }
    int main()
    {
        cin>>n;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>h[i][j];
                
        int peak = 0,valley = 0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++) 
            {
                if(!st[i][j])
                {
                    bool has_peak = false,has_valley = false;
                    bfs(i,j,has_peak,has_valley);
                    if(!has_valley) valley ++;
                    if(!has_peak) peak++;
                }
            }
        }
        cout<<peak<<" "<<valley<<endl;
    }