2 条题解

  • 0
    @ 2025-10-8 17:02:57
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1010;
    int n,h[N][N],w;//w==1谷 , w==2峰 
    bool vis[N][N];
    int dx[8]={-1,-1,-1,0,0,1,1,1};
    int dy[8]={-1,0,1,-1,1,-1,0,1};
    void dfs(int x,int y)
    {
    	vis[x][y]=1; //标记当前点已访问
        for(int i=0;i<8;i++)//搜索与当前点相邻的8个点
        {
            int xx=x+dx[i],yy=y+dy[i];
            if(!(xx>=1&&xx<=n&&yy>=1&&yy<=n))continue;
            if(h[xx][yy]==h[x][y]&&vis[xx][yy]==0) dfs(xx,yy);
            else if( (h[xx][yy]<h[x][y]&&w==1) ||
    		         (h[xx][yy]>h[x][y]&&w==2)  ) //周围既有比它高的又有比它低的 则它什么也不是,为-1
    					w=-1;
    
            else if(w==0)//没确定是是峰还是谷,为0。搜到与当前搜索高度不同的点 暂且标记当前搜索区域是峰还是谷
            {
                if(h[xx][yy]<h[x][y])w=2;
                if(h[xx][yy]>h[x][y])w=1;
            }
        }
    }
    int main()
    {
        scanf("%d",&n);    
        bool bk=1;int v=-1;
    	for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
    		{
                scanf("%d",&h[i][j]);
    			if(v==-1)v=h[i][j];
    			if(h[i][j]!=v)bk=0; //如果有高度不相同的点
    		}
    	if(bk){printf("1 1\n");return 0;}	
        
    	memset(vis,0,sizeof(vis));
    	int a=0,b=0; //a表示山峰个数,b表示山谷个数
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(vis[i][j]==0)//找到一个没搜过的点开始搜索
                {
    				w=0; //w=0表示当前点还没确定是山峰还是山谷
                    dfs(i,j);
                    if(w==1)a++;
                    else if(w==2)b++;
                }
        printf("%d %d\n",b,a);
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:02:43
      #include<bits/stdc++.h>
      using namespace std;
      const int N=1010;
      int n,h[N][N],w;//w==1谷 , w==2峰 
      bool vis[N][N];
      int dx[8]={-1,-1,-1,0,0,1,1,1};
      int dy[8]={-1,0,1,-1,1,-1,0,1};
      void dfs(int x,int y)
      {
      	vis[x][y]=1; //标记当前点已访问
          for(int i=0;i<8;i++)//搜索与当前点相邻的8个点
          {
              int xx=x+dx[i],yy=y+dy[i];
              if(!(xx>=1&&xx<=n&&yy>=1&&yy<=n))continue;
              if(h[xx][yy]==h[x][y]&&vis[xx][yy]==0) dfs(xx,yy);
              else if( (h[xx][yy]<h[x][y]&&w==1) ||
      		         (h[xx][yy]>h[x][y]&&w==2)  ) //周围既有比它高的又有比它低的 则它什么也不是,为-1
      					w=-1;
      
              else if(w==0)//没确定是是峰还是谷,为0。搜到与当前搜索高度不同的点 暂且标记当前搜索区域是峰还是谷
              {
                  if(h[xx][yy]<h[x][y])w=2;
                  if(h[xx][yy]>h[x][y])w=1;
              }
          }
      }
      int main()
      {
          scanf("%d",&n);    
          bool bk=1;int v=-1;
      	for(int i=1;i<=n;i++)
              for(int j=1;j<=n;j++)
      		{
                  scanf("%d",&h[i][j]);
      			if(v==-1)v=h[i][j];
      			if(h[i][j]!=v)bk=0; //如果有高度不相同的点
      		}
      	if(bk){printf("1 1\n");return 0;}	
          
      	memset(vis,0,sizeof(vis));
      	int a=0,b=0; //a表示山峰个数,b表示山谷个数
          for(int i=1;i<=n;i++)
              for(int j=1;j<=n;j++)
                  if(vis[i][j]==0)//找到一个没搜过的点开始搜索
                  {
      				w=0; //w=0表示当前点还没确定是山峰还是山谷
                      dfs(i,j);
                      if(w==1)a++;
                      else if(w==2)b++;
                  }
          printf("%d %d\n",b,a);
          return 0;
      }
      • 1

      「POI2007 R2」山峰和山谷 Ridges and Valleys

      信息

      ID
      2755
      时间
      2000ms
      内存
      64MiB
      难度
      6
      标签
      递交数
      22
      已通过
      11
      上传者