山峰和山谷

解题思路

一道bfs
每次从一个没有访问过的点开始
当周围有点相等
就继续访问
否则就判断它周围的点与这个区间点的大小

AC代码

#include<cstdio>
using namespace std;
int n,answer1,answer2,px[1000005],py[1000005],c[1005][1005],w[1005][1005];
int dx[8]={
   0,0,1,-1,1,-1,1,-1};
int dy[8]={
   1,-1,0,0,-1,-1,1,1};
bool check(int x,int y)//判断是否出界
{
   
	if(x>=1&x<=n&&y>=1&&y<=n)return true;
	return false;
}
void bfs(int x,int y)
{
   
	int ok1=0,ok2=0,head=0,tail=0,num=w[x][y];//初值
	px[++tail]=x;
	py[tail]=y;
	c[x][y]=1;
	while(head<tail)//bfs
	{
   
		head++;
		for(int i=0;i<8;i++)
		{
   
			int xx=dx[i]+px[head],yy=dy[i]+py[head];
			if(check(xx,yy))
			{
   
				if(w[xx][yy]==num)
				{
   
					if(c[xx][yy]==0)c[xx][yy]=1,px[++tail]=xx,py[tail]=yy;
				}
				else 
				{
   
				 	if(w[xx][yy]<num)ok1=1;
				 	if(w[xx][yy]>num)ok2=1;
				}
			}
		}
	}
	if(ok1==0&&ok2==0)answer1++,answer2++;//判断
	if(ok1==1&&ok2==0)answer1++;
	if(ok1==0&&ok2==1)answer2++;
	return;
}
int main()
{
   
	scanf("%d",&n);//输入
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  scanf("%d",&w[i][j]);
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  if(c[i][j]==0)bfs(i,j);
	printf("%d %d",answer1,answer2);  
	return 0;
}
 

谢谢