B. 【例题2】山峰和山谷

在这里插入图片描述

题解

先解释一下样例：

红笔圈着的是两个山峰，其余的形成一个山谷。

每次从未访问过的点开始BFS，对它相邻的点（八连通）进行搜索：

若搜索的点等于当前点，则加入队列

若搜索的点大于当前点，则标记它不可能为山峰

若搜索的点小于当前点，则标记它不可能为山谷

代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int n,a[1001][1001],ans1,ans2;int dx[8]= {
   0,0,1,-1,1,1,-1,-1};int dy[8]= {
   1,-1,0,0,1,-1,1,-1};bool f[1001][1001];struct node//结构体表示坐标{
   	int x,y;};bool check(int x,int y)//检查是否越界{
   	if(x>0&&y>0&&x<=n&&y<=n) return 1;	else return 0; }void bfs(int x,int y){
   	f[x][y]=1;//标记为访问过	queue
       
         q;	q.push(node {
   x,y});	bool hill=true,low=true;	do	{
   		node j=q.front();		q.pop();		for(int i=0; i<8; i++)		{
   			int xx=j.x+dx[i],yy=j.y+dy[i];			if(check(xx,yy))			{
   				if(a[xx][yy]==a[j.x][j.y])//若搜索的点等于当前点，则加入队列				{
   					if(!f[xx][yy])					{
   						f[xx][yy]=1;//标记为访问过						q.push(node {
   xx,yy});					}				}				else				{
   					if(a[xx][yy]>a[j.x][j.y]) hill=false;//若搜索的点大于当前点，则标记它不可能为山峰					if(a[xx][yy]
        
         >n; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>a[i][j];}void work(){ for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(!f[i][j]) bfs(i,j);}void out(){ cout<
         
          <<" "<