http://www.zybbs.org/JudgeOnline/problem.php?id=1102
八中题目描述太DT了……还是看这里：
http://main.edu.pl/en/archive/oi/14/grz
水题不解释……（我颓废了）
bfs记录一下高度相同的联通块，然后暴力枚举联通块的周围有木有比他还高（矮）的……完了……
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int px[8]={-1,-1,0,1,1,1,0,-1};
const int py[8]={0,1,1,1,0,-1,-1,-1};
int map[1001][1001],x[1000001],y[1000001],n,valleys,ridges;
bool vis[1001][1001];
bool check(int pos,char sym){
for(int k=1;k<=pos;k++)
for(int i=0;i<8;i++){
int xx=x[k]+px[i],yy=y[k]+py[i];
if(!(xx>0&&xx<=n&&yy>0&&yy<=n)) continue;
if((sym=='v'&&map[xx][yy]<map[x[k]][y[k]])||(sym=='r'&&map[xx][yy]>map[x[k]][y[k]])) return false;
}
return true;
}
void bfs(int posx,int posy){
int head=1,tail=0,xx,yy;
x[++tail]=posx,y[tail]=posy;
while(head<=tail){
for(int i=0;i<8;i++){
xx=x[head]+px[i],yy=y[head]+py[i];
if(!(xx>0&&xx<=n&&yy>0&&yy<=n&&map[xx][yy]==map[posx][posy]&&!vis[xx][yy])) continue;
vis[xx][yy]=true;
x[++tail]=xx,y[tail]=yy;
}
head++;
}
if(check(tail,'v')) valleys++;
if(check(tail,'r')) ridges++;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) scanf("%d",&map[i][j]);
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!vis[i][j]) bfs(i,j);
printf("%d %d\n",ridges,valleys);
return 0;
}
