Description
有一个居住在多山岛屿的登山家，已经攀上了一座山峰，并且要攀爬另外一座更高的山峰。
更精确地说，岛上的每一点都有一个大于零的海拔（海面的海拔为零），并且如果登山家位于海拔Ei的山峰上，那么他的目标是到达其他海拔为Ej（Ej>Ei）的山峰。因为登山家在一个山峰上，所以无法马上向上爬——为了到达一个海拔更高的地点，登山家需要先下山才能上山。下山的路不及上山精彩，因此，登山家想将从当前地点到达更高山峰途中最低点的海拔最大化。
例如，如果岛屿的轮廓如图中所示，并且登山家在海拔为E4的山峰，那么有三个山峰有更高的海拔（E5,E6和E7），但是路途中最低点最高的路径是到达海拔E7的山峰的路径——在路上他不会走到海拔E2以下（在其他路径中他必须经过海拔E1的地点）。如果他从海拔E5的山峰出发，那么对应路径经过的最低海拔为E3（到达E6的路径），但是如果他从E6 出发，那么最低点就是E1。
岛屿的地图是一个二维的N*M的矩形网格，并且描述了岛屿每一部分的海拔——格子里的数字表示岛屿对应地区的海拔。如果两个各自有公共点，那么他们相邻。因此，每个格子（除了在边界上的）和其他8个格子相邻。一条路径是一系列的格子，序列中连续的两个格子相邻。一个“*区域”是一个相同海拔格子的集合，并且集合中任意两个格子能够用仅经过这个集合内格子的路径连接。任意两个等高的相邻格子属于同一“*区域” 。一座山峰，是一个相邻的格子中没有更高海拔的“*区域”。
写一个程序，找到所有山峰，并且计算每个山峰到达更高山峰路途中最大的最低海拔。对于岛上最高的山峰（岛上没有更高的山峰），可以确定登山家会离开岛屿寻找更高的山峰，因此，路途中的最低海拔为零（海*面的海拔）。
Input
输入的第一行包含两个整数N和M（1<=N,M<=2000，N*M<=10^5），分别是地图的高和宽。
接下来N行包含岛屿地图的描述。其中每行包含M个空格隔开的整数Eij（1<=Eij<=10^6）。格子Eij（对应地图的i 行j 列）的海拔为输入的i+1行第j 个整数。
Output
输出的第一行须包含一个整数P，岛屿中山峰的个数。接下来P行须每行包含两个整数：这座山峰的海拔及到达更高山峰途中最低点海拔的最大值。这些山峰的信息按照海拔降序输出；如果若干座山峰海拔相同，那么它们按照那个最低点的海拔降序输出。
Sample Input
输入1：
6 6
21 16 9 11 6 7
21 21 10 14 15 9
18 20 8 9 13 14
11 10 9 9 8 13
8 12 12 14 13 8
7 13 12 9 5 1
输入2：
5 3
16 14 16
14 14 15
12 17 16
12 13 10
16 11 16
Sample Output
输出1：
4
21 0
15 11
14 13
13 12
输出2：
5
17 0
16 15
16 14
16 13
16 13
Data Constraint
• 15 分的数据中N<=2或M<=2。
• 50 分的数据中有P<=500。
• 80 分的数据中有P<=5000。
题解
先将通高*区域进行合并
将所有的*区域按照从高到低排个序，依次按高到低的顺序加进图中，如果邻*的*区域都没被加入进图中，那么这个*区域一定是山峰。否则这个*区域属于比自己高的邻*的山峰。
如果一个*区域同时被属于多个山峰，那么除了最高的峰外，其他的峰都找到了一条到达更高的峰的路径，且这个*区域就是路径上高度最高的最低值（比这个最低值更低的还没有被加进图中呢）。这个时候，将小的峰往大的峰合并。
其他的峰他们的答案一定相同，所以可以用启发式合并。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int z[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int fx,fy,l,n,m,t,s,num,h,x,y,xx,yy,tot,sf,v[2003][2003],visit[2003][2003],g[100003],ans[100003][2],k[100003],fa[100003],p[100003],d[2003][2003],fb[100003],go[100003*2],head[100003],next[100003*2],nx[100003*2],ny[100003*2];
bool bz[100003],b[100003];
bool cmp(int x,int y){return k[x]>k[y];}
void insert(int a,int b,int x,int y)
{
go[++tot]=b;
next[tot]=head[a];
head[a]=tot;
nx[tot]=x;
ny[tot]=y;
}
int getfather(int x){if (fa[x]==x) return x; else {fa[x]=getfather(fa[x]); return fa[x];}}
void kz(int x,int y)
{
visit[x][y]=num;
insert(num,d[x][y],x,y);
for (int i=0;i<=7;i++)
{
int xx=x+z[i][0],yy=y+z[i][1];
if (xx>=1&&x<=n&&y>=1&&y<=m&&!visit[xx][yy])
if (v[x][y]==v[xx][yy]) kz(xx,yy);
}
}
void qsort(int l,int r)
{
if (l>=r) return;
int i=l,j=r,midx=ans[(i+j)/2][0],midy=ans[(i+j)/2][1];
while (i<j)
{
while (ans[i][0]>midx||(ans[i][0]==midx&&ans[i][1]>midy)) i++;
while (ans[j][0]<midx||(ans[j][0]==midx&&ans[j][1]<midy)) j--;
if (i<=j)
{
swap(ans[i],ans[j]);
i++; j--;
}
}
qsort(l,j);
qsort(i,r);
}
int main()
{
//freopen("peaks.in","r",stdin);
//freopen("peaks.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
num++;
scanf("%d",&v[i][j]);
d[i][j]=num;
}
num=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (!visit[i][j])
{
num++;
kz(i,j);
k[num]=v[i][j];
}
for (int i=1;i<=num;i++) p[i]=i;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int o=0;o<=7;o++)
{
x=i+z[o][0]; y=j+z[o][1];
if (v[x][y]>v[i][j]) bz[visit[i][j]]=1;
}
for (int i=1;i<=num;i++) if (!bz[i]) fb[i]=1;
sort(p+1,p+num+1,cmp);
for (int i=1;i<=num;i++) fa[i]=i;
for(int i=1;i<=num;i++)
{
h=p[i];
b[h]=1;
for (int j=head[h];j;j=next[j])
{
x=nx[j];y=ny[j];
for (int o=0;o<=7;o++)
{
xx=x+z[o][0]; yy=y+z[o][1];
if (visit[xx][yy]!=h&&b[visit[xx][yy]])
{
fx=getfather(visit[xx][yy]);
fy=getfather(h);
if (fx!=fy)
if (k[fx]==k[fy])
{
fa[fy]=fx;
fb[fx]+=fb[fy];
}
else
if (k[fx]>k[fy])
{
fa[fy]=fx;
for (int q=1;q<=fb[fy];q++)
{
sf++;
ans[sf][0]=k[fy];
ans[sf][1]=k[h];
}
}
else
if (k[fx]<k[fy])
{
fa[fx]=fy;
for (int q=1;q<=fb[fx];q++)
{
sf++;
ans[sf][0]=k[fx];
ans[sf][1]=k[h];
}
}
}
}
}
}
fx=getfather(num);
for (int i=1;i<=fb[fx];i++) ans[++sf][0]=k[fx];
printf("%d
",sf);
qsort(1,sf);
for (int i=1;i<=sf;i++) printf("%d %d
",ans[i][0],ans[i][1]);
return 0;
}