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\n",sf);qsort(1,sf);for (int i=1;i<=sf;i++) printf("%d %d\n",ans[i][0],ans[i][1]);return 0; }

轉載于:https://www.cnblogs.com/Comfortable/p/8412231.html

總結

以上是生活随笔為你收集整理的[并查集][排序][dfs][启发式合并] JZOJ P3635 Peaks的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。