2 solutions

  • -1
    @ 2024-7-29 11:12:44
    #include<bits/stdc++.h>
    using namespace std;
    typedef pair<int,int> PII;
    #define x first
    #define y second
    const int N=1010;
    bool st[N][N];
    int dx[]={0,1,0,-1,1,1,-1,-1};
    int dy[]={1,0,-1,0,1,-1,1,-1};
    int g[N][N];
    int main()
    {
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			cin>>g[i][j];
    		}
    	}
    	int a=0,b=0; //山峰和山谷的数目 
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			if(!st[i][j])
    			{
    				queue<PII> q;
    				q.push({i,j});
    				st[i][j]=1;
    				int h=0,l=0;
    				while(q.size())
    				{
    					PII t=q.front();
    					q.pop();
    					for(int k=0;k<8;k++)
    					{
    						int tx=t.x+dx[k],ty=t.y+dy[k];
    						if(tx<=0||tx>n||ty<=0||ty>n) continue;
    						if(g[tx][ty]!=g[t.x][t.y]) //不相同 
    						{
    							if(g[t.x][t.y]<g[tx][ty]) l=1; //存在某个点比当前点高(一定不是山峰) 
    							else h=1; // 存在某个点比当前点底(一定不是山谷) 
    						}
    						else if(!st[tx][ty])
    						{
    							st[tx][ty]=1;
    							q.push({tx,ty});
    						}
    					}
    				}
    				if(!h) b++; //可以是山谷 
    				if(!l) a++; //可以是山峰 
    			}
    		}
    	}
    	cout<<a<<" "<<b;
        return 0;
    }
    
    
    • -2
      @ 2024-7-11 10:42:59
      #include
      using namespace std;
      typedef pair<int,int> PII;
      #define x first
      #define y second
      const int N=1010;
      bool st[N][N];
      int dx[]={0,1,0,-1,1,1,-1,-1};
      int dy[]={1,0,-1,0,1,-1,1,-1};
      int g[N][N];
      int main()
      {
      	int n;
      	cin>>n;
      	for(int i=1;i<=n;i++)
      	{
      		for(int j=1;j<=n;j++)
      		{
      			cin>>g[i][j];
      		}
      	}
      	int a=0,b=0;
      	for(int i=1;i<=n;i++)
      	{
      		for(int j=1;j<=n;j++)
      		{
      			if(!st[i][j])
      			{
      				queue<PII> q;
      				q.push({i,j});
      				st[i][j]=1;
      				int h=0,l=0;
      				while(q.size())
      				{
      					PII t=q.front();
      					q.pop();
      					for(int k=0;k<8;k++)
      					{
      						int tx=t.x+dx[k],ty=t.y+dy[k];
      						if(tx<=0||tx>n||ty<=0||ty>n) continue;
      						if(g[tx][ty]!=g[t.x][t.y])
      						{
      							if(g[t.x][t.y]<g[tx][ty]) l=1;
      							else h=1;
      						}
      						else if(!st[tx][ty])
      						{
      							st[tx][ty]=1;
      							q.push({tx,ty});
      						}
      					}
      				}
      				if(!h) b++;
      				if(!l) a++;
      			}
      		}
      	}
      	cout<<a<<" "<<b;
          return 0;
      }
      
      
      • 1

      Information

      ID
      226
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      7
      Tags
      # Submissions
      27
      Accepted
      5
      Uploaded By