# 90分了
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,mapn[1001][1001],ridge_sum,valley_sum;
bool visit[1001][1001];
short direx[]={0,0,1,-1,1,1,-1,-1};
short direy[]={1,-1,0,0,1,-1,1,-1};
struct Point {int x,y;};
bool in_scp(int bef,int ob,int aft)
{return bef<=ob && ob<=aft;}
bool in_area(int x,int y)
{return in_scp(1,x,n) && in_scp(1,y,n);}
bool on_boundary(int x,int y)
{return x==1 || x==n || y==1 || y==n;}
bool BFS(int x,int y,bool ridge)
{
queue<Point> Q;
Q.push(Point{x,y});
while(!Q.empty())
{
Point now=Q.front();
Q.pop();
if(visit[now.y][now.x]) continue;
visit[now.y][now.x]=1;
for(short i=0;i<8;i++)
if
(
(
(mapn[now.y+direy[i]][now.x+direx[i]]>mapn[now.y][now.x] && ridge)
||
(mapn[now.y+direy[i]][now.x+direx[i]]<mapn[now.y][now.x] && !ridge)
)
&& in_area(now.x+direx[i],now.y+direy[i])
)return 0;
for(short i=0;i<8;i++)
if
(
!visit[now.y+direy[i]][now.x+direx[i]]
&&
in_area(now.x+direx[i],now.y+direy[i])
&&
mapn[now.y+direy[i]][now.x+direx[i]]==mapn[now.y][now.x]
)Q.push(Point{now.x+direx[i],now.y+direy[i]});
}
return 1;
}
int main()
{
scanf("%d",&n);
bool plain=1;
int test;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&mapn[i][j]);
if(i==j && j==1) test=mapn[i][j];
else if(mapn[i][j]!=test) plain=0;
test=mapn[i][j];
}
if(plain) {cout<<"1 1";return 0;}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!visit[i][j])
for(short f=0;f<8;f++)
if(in_area(j+direx[f],i+direy[f]))
{
bool type=(mapn[i][j]>=mapn[i+direy[f]][j+direx[f]]);
if(BFS(j,i,type))
if(type) ridge_sum++;
else valley_sum++;
break;
}
cout<<ridge_sum<<' '<<valley_sum;
return 0;
}
```
### 改成BFS了,但还是有问题,马上就要从机房出去了,下次再改……
by Seauy @ 2018-12-20 17:25:11