译自 POI 2007 Stage 2. Day 0「Ridges and Valleys」

给定一个 n \times nn×n 的网格状地图，每个方格 (i,j)(i,j) 有一个高度 w_{ij}wij​。如果两个方格有公共顶点，则它们是相邻的。

定义山峰和山谷如下：

• 均由地图上的一个连通块组成；
• 所有方格高度都相同；
• 周围的方格（即不属于山峰或山谷但与山峰或山谷相邻的格子）高度均大于山谷的高度，或小于山峰的高度。

求地图内山峰和山谷的数量。特别地，如果整个地图方格的高度均相同，则整个地图既是一个山谷，也是一个山峰。

第一行一个整数 nn （2 \le n \le 10002≤n≤1000），表示地图的大小。

接下来 nn 行每行 nn 个整数表示地图。第 ii 行有 nn 个整数 w_{i1}, w_{i2}, \ldots, w_{in} (0 \le w_{ij} \le 1\ 000\ 000\ 000)wi1​,wi2​,…,win​(0≤wij​≤1 000 000 000)，表示地图第 ii 行格子的高度。

输出一行两个整数，分别表示山峰和山谷的数量。

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

2 1

5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7

3 3

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

struct node{
	int x,y;
};
struct node mov[8]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};

int map[1005][1005];
int vis[1005][1005];
int h=0,l=0;
int hight,low;
int tx,ty,nx,ny,n;

void bfs(int x,int y)
{
	queue<int> qx,qy;
	qx.push(x);qy.push(y);
	vis[x][y]=1;
	while(!qx.empty()&&!qy.empty())
	{
		tx=qx.front(),qx.pop();
		ty=qy.front(),qy.pop();
		for(int i=0;i<=7;i++)
		{
			nx=tx+mov[i].x;
			ny=ty+mov[i].y;
			if(nx>=0&&nx<n&&ny>=0&&ny<n)
			{
				if(map[x][y]<map[nx][ny])
				{
					hight=0;
				}
				else if(map[x][y]>map[nx][ny])
				{
					low=0;
				}
				else if(map[x][y]==map[nx][ny]&&vis[nx][ny]==0)
				{
					qx.push(nx);
					qy.push(ny);
					vis[nx][ny]=1;
				}
			}
			/*if(!hight && !low)
			{
				return;
			}*/
		}
	}
}

/*int check(int x,int y)//检查这个点所在连通块是不是以前已经搜过了，搜了明显没必要再搜了
{//如果搜过返回0，没搜返回1
	for(int i=0;i<=7;i++)
	{
		nx=tx+mov[i].x;
		ny=ty+mov[i].y;
		if(nx>=0&&nx<n&&ny>=0&&ny<n)
		{
			if(map[x][y]==map[nx][ny]&&vis[nx][ny]==1)
			{
				vis[x][y]=1;
				return 0;
			}
		}
	}
	return 1;
}*/

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf("%d",&map[i][j]);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(!vis[i][j]){
				hight=1,low=1;
				bfs(i,j);
				h+=hight;
				l+=low;
			}
		}
	}
	printf("%d %d\n",h,l);
	return 0;
}