题目描述

做法比较麻烦，具体的做法为先找每个连通块，判断每个连通块的点是不是满足山谷/山峰的要求

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N=1010;
int w[N][N];
int st[N][N];
typedef pair<int, int> PII;
int n,m;

int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};

int find_low(int x,int y,int h)
{
    //山峰返回1，山谷和山脉返回0
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=1 && a<=n &&b>=1 &&b<=n &&w[a][b]>h)
        {
            return 0;
        }
    }
    return 1;
}

int find_high(int x,int y,int h)
{
    //山谷返回1，山峰和山脉返回0
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=1 && a<=n &&b>=1 &&b<=n &&w[a][b]<h)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>w[i][j];
        }
    }
    queue<PII> q;
    int res_top=0;
    int res_low=0;
    int flag;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            flag=0;
            if(st[i][j]==0)
            {
                q.push({i,j});
                //记录这个点的高度
                int h=w[i][j];
                st[i][j]=1;
                //开始找和这个点等高的点
                //假设这个连通图是山谷
                flag=1;
                while(q.size())
                {
                    auto t=q.front();
                    q.pop();
                    if(find_high(t.first,t.second,h)==0)
                    {
                        flag=0;
                    }
                    for(int k=0;k<8;k++)
                    {
                        int a=t.first+dx[k];
                        int b=t.second+dy[k];

                        if(a>=1 && a<=n &&b>=1 &&b<=n &&w[a][b]==h && st[a][b]==0)
                        {
                            st[a][b]=1;
                            q.push({a,b});
                        }

                    }
                }
                //break;
            }
            if(flag==1)
            res_top++;
        }
    }

    memset(st,0,sizeof st);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            flag=0;
            if(st[i][j]==0)
            {
                q.push({i,j});
                //记录这个点的高度
                int h=w[i][j];
                st[i][j]=1;
                //开始找和这个点等高的点
                //假设这个连通图是山谷
                flag=1;
                while(q.size())
                {
                    auto t=q.front();
                    q.pop();
                    if(find_low(t.first,t.second,h)==0)
                    {
                        flag=0;
                    }
                    for(int k=0;k<8;k++)
                    {
                        int a=t.first+dx[k];
                        int b=t.second+dy[k];

                        if(a>=1 && a<=n &&b>=1 &&b<=n &&w[a][b]==h && st[a][b]==0)
                        {
                            st[a][b]=1;
                            q.push({a,b});
                        }

                    }
                }
                //break;
            }
            if(flag==1)
            res_low++;
        }
    }
    cout<<res_low<<" "<<res_top;

    return 0;



}

二刷，有一个小坑，就是中间如果找到了不满足的山，不能break，因为要先把高度等于这个山的全标记了

如果提前break，会导致队列没有清空干净，导致上一个ij中剩的元素还在队列中，这样在取队头的时候，会取到上一个连通块中的元素，导致再进行find的时候出问题

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=1010;
typedef pair<int,int> pii;
queue<pii> q;

int w[N][N];
int num_sf,num_sg;
int st[N][N];
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};
int n;

//判断这个点可不可以称为山谷,1可以，0不可以
int find_nohigh(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=n)
        {
            if(w[a][b]<w[x][y])
            {
                return 0;
            }
        }
    }
    return 1;
}

//判断这个点可不可以称为山峰,1可以，0不可以
int find_nolow(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=n)
        {
            if(w[a][b]>w[x][y])
            {
                return 0;
            }
        }
    }
    return 1;
}


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int flag=1;
            if(st[i][j]==0)
            {
                int cur_high=w[i][j];
                st[i][j]=1;
                q.push({i,j});
                while(q.size())
                {
                    auto t=q.front();
                    int x=t.first;
                    int y=t.second;
                    q.pop();
                    if(find_nolow(x,y)==0)
                    {
                        flag=0;
                        //break;
                    }
                    for(int k=0;k<8;k++)
                    {
                        int a=x+dx[k];
                        int b=y+dy[k];
                        if(a>=1&&a<=n&&b>=1&&b<=n && st[a][b]==0 &&w[a][b]==cur_high)
                        {
                            st[a][b]=1;
                            q.push({a,b});
                        }
                    }
                }
                if(flag==1)
                {
                    num_sf++;
                }
            }


        }
    }
    memset(st,0,sizeof st);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int flag=1;
            if(st[i][j]==0)
            {
                int cur_high=w[i][j];
                st[i][j]=1;
                q.push({i,j});
                while(q.size())
                {
                    auto t=q.front();
                    int x=t.first;
                    int y=t.second;
                    q.pop();
                    if(find_nohigh(x,y)==0)
                    {
                        flag=0;
                        //注意此处不能break！！因为后面还要做st操作，最后把这组“山”不计数就行了，但也要做后面的st
                        //break;
                    }
                    for(int k=0;k<8;k++)
                    {
                        int a=x+dx[k];
                        int b=y+dy[k];
                        if(a>=1&&a<=n&&b>=1&&b<=n && st[a][b]==0 &&w[a][b]==cur_high)
                        {
                            st[a][b]=1;
                            q.push({a,b});
                        }
                    }
                }
                if(flag==1)
                {
                    num_sg++;
                }
            }
        }
    }
    cout<<num_sf<<" "<<num_sg;

    return 0;
}

2023/12/1

bfs, 一遍过
比较麻烦，按题目意思一步一步走即可，具体思路如下：
1. 对于一个点，先判断它是否被遍历过
2. 如果未遍历过，则对它进行bfs
3. 先遍历它周围所有高度不等于它的点，判断该高度是山峰还是山谷
4. 如果出现矛盾，则既不算山峰也不算山谷
5. 再遍历高度等于它的点，将其入队

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N=1010;

int dx[]={0,1,1,1,0,-1,-1,-1};
int dy[]={1,1,0,-1,-1,-1,0,1};

int n;
int g[N][N];
int st[N][N];

typedef pair<int,int> pii;
queue<pii> q;

int sg, sf;


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] == 0)
            {
                int h = g[i][j];
                q.push({i,j});
                st[i][j] = 1;

                // 几个标志位
                int mt = 0;     // mt为1代表是山谷，为2代表是山峰，0代表初始状态， 3代表矛盾状态(既不是山顶也不是山峰)
                int flag = 0;   // flag = 1代表这一片已经被定义为山谷或山峰，flag=0代表还没被定义

                // bfs搜索该点周围的所有点
                while(q.size())
                {
                    auto t = q.front();
                    q.pop();
                    int x = t.first;
                    int y = t.second;

                    // 先判断该点周围的其他点是大于它还是小于它
                    for(int k=0;k<8;k++)
                    {
                        int a = x+dx[k];
                        int b = y+dy[k];

                        if(a>=1 && b>=1 && a<=n && b<=n && g[a][b] != h)
                        {
                            // 出现矛盾
                            if((g[a][b] < h && flag == 1 && mt ==1) || (g[a][b] > h && flag == 1 && mt ==2))
                            {
                                mt = 3;
                            }

                            if(g[a][b] < h && flag == 0)
                            {
                                mt = 2;
                                flag = 1;
                            }
                            else if(g[a][b] > h && flag == 0)
                            {
                                mt = 1;
                                flag = 1;
                            }
                        }
                    }

                    // bfs周围高度等于h的点
                    for(int k=0;k<8;k++)
                    {
                        int a = x+dx[k];
                        int b = y+dy[k];

                        if(a>=1 && b>=1 && a<=n && b<=n && g[a][b] == h && st[a][b] == 0)
                        {
                            q.push({a, b});
                            st[a][b] = 1;
                        }
                    }
                }

                // 在遍历完之后，根据结果，分情况计算
                if(mt == 1 && flag == 1)
                {
                    sg++;
                }
                else if(mt == 2 && flag == 1)
                {
                    sf++;
                }
                else if(flag == 0)
                {
                    sg++;
                    sf++;
                }

            }
        }
    }

    cout<<sf<<" "<<sg;

    return 0;
}