╰( ̄▽ ̄)╭
有一个居住在多山岛屿的登山家,已经攀上了一座山峰,并且要攀爬另外一座更高的山峰。
更精确地说,岛上的每一点都有一个大于零的海拔(海面的海拔为零),并且如果登山家位于海拔Ei的山峰上,那么他的目标是到达其他海拔为Ej(Ej>Ei)的山峰。因为登山家在一个山峰上,所以无法马上向上爬——为了到达一个海拔更高的地点,登山家需要先下山才能上山。下山的路不及上山精彩,因此,登山家想将从当前地点到达更高山峰途中最低点的海拔最大化。
例如,如果岛屿的轮廓如图中所示,并且登山家在海拔为E4的山峰,那么有三个山峰有更高的海拔(E5,E6和E7),但是路途中最低点最高的路径是到达海拔E7的山峰的路径——在路上他不会走到海拔E2以下(在其他路径中他必须经过海拔E1的地点)。如果他从海拔E5的山峰出发,那么对应路径经过的最低海拔为E3(到达E6的路径),但是如果他从E6 出发,那么最低点就是E1。
岛屿的地图是一个二维的N*M的矩形网格,并且描述了岛屿每一部分的海拔——格子里的数字表示岛屿对应地区的海拔。如果两个各自有公共点,那么他们相邻。因此,每个格子(除了在边界上的)和其他8个格子相邻。一条路径是一系列的格子,序列中连续的两个格子相邻。一个“平区域”是一个相同海拔格子的集合,并且集合中任意两个格子能够用仅经过这个集合内格子的路径连接。任意两个等高的相邻格子属于同一“平区域” 。一座山峰,是一个相邻的格子中没有更高海拔的“平区域”。
写一个程序,找到所有山峰,并且计算每个山峰到达更高山峰路途中最大的最低海拔。对于岛上最高的山峰(岛上没有更高的山峰),可以确定登山家会离开岛屿寻找更高的山峰,因此,路途中的最低海拔为零(海平面的海拔)。
1<=N,M<=2000,N∗M<=105,1<=Eij<=106
(⊙ ▽ ⊙)
先把网格按高度从大到小排序, 然后依次插入网格。
每次插入网格
C
后,询问其相邻的网格;
若其相邻的网格存在已被访问过的,那么这个网格所在的“平区域”肯定不是峰;
同时可以更新其相邻的网格所在的峰的答案。
否则C就是峰。
细节很多,特判很多,出题人是SB。
( ̄~ ̄)
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#define ll long long
#define pos(x,y) (((x)-1)*m+(y))
using namespace std;
const char* fin=
"peaks.in";
const char* fout=
"peaks.out";
const int inf=
0x7fffffff;
const int maxn=
100007,maxm=
2006;
const int f[
8][
2]={{
0,
1},{
1,
1},{
1,
0},{-
1,
0},{-
1,-
1},{
0,-
1},{
1,-
1},{-
1,
1}};
int n,m,i,j,k,tot,xx;
int a[maxm][maxm],rf[maxm][maxm],go[maxm*maxm],Rf[maxm*maxm];
bool bz[maxm][maxm];
int dad[maxn];
int ans1;
struct node{
int x,y,z,ans;
int feng;
}b[maxn],ans[maxn];
bool cmp(
const node &a,
const node &b){
return a.z>b.z || (a.z==b.z && a.x<b.x) || (a.z==b.z && a.x==b.x && a.y<b.y);
}
bool cmp1(node a,node b){
return a.feng>b.feng || (a.feng==b.feng && a.z>b.z) || (a.feng==b.feng && a.z==b.z && a.ans>b.ans);
}
bool cmp2(node a,node b){
return a.x>b.x || (a.x==b.x && a.y>b.y);
}
int getdad(
int v){
if (!dad[v])
return v;
dad[v]=getdad(dad[v]);
return dad[v];
}
int getgo(
int v){
if (!go[v])
return v;
go[v]=getgo(go[v]);
return go[v];
}
void merge(
int v,
int u){
int j=getdad(v),k=getdad(u);
dad[j]=k;
}
int main(){
freopen(fin,
"r",stdin);
freopen(fout,
"w",stdout);
scanf(
"%d%d",&n,&m);
k=
0;
for (i=
1;i<=n;i++)
for (j=
1;j<=m;j++){
scanf(
"%d",&a[i][j]);
b[++tot].x=i;
b[tot].y=j;
b[tot].z=a[i][j];
}
sort(b+
1,b+tot+
1,cmp);
for (i=
1;i<=tot;i++) rf[b[i].x][b[i].y]=i;
for (i=
1;i<=tot;i++){
b[i].feng=
1;
for (j=
0;j<
8;j++){
int X=b[i].x+f[j][
0],Y=b[i].y+f[j][
1];
if (X>
0 && X<=n && Y>
0 && Y<=m){
if (bz[X][Y]){
b[i].feng=
0;
int tmp=getdad(rf[b[i].x][b[i].y]);
int tmd=getdad(rf[X][Y]);
if (b[tmp].z>b[tmd].z){
if (tmp!=tmd){
dad[tmd]=tmp;
b[tmd].ans=max(b[tmd].ans,b[i].z);
}
}
else{
if (tmp!=tmd){
dad[tmp]=tmd;
if (b[tmp].z!=b[tmd].z){
b[tmp].ans=max(b[tmp].ans,b[i].z);
}
else{
if (b[i].z==b[tmp].z) b[tmp].feng=
0;
go[pos(b[tmp].x,b[tmp].y)]=pos(b[tmd].x,b[tmd].y);
}
}
}
}
}
}
bz[b[i].x][b[i].y]=
true;
}
sort(b+
1,b+tot+
1,cmp1);
for (i=
1;i<=tot;i++) Rf[pos(b[i].x,b[i].y)]=i;
for (i=
1;i<=tot;i++){
if (!b[i].feng)
break;
if (b[i].z==b[Rf[getgo(pos(b[i].x,b[i].y))]].ans){
continue;
}
ans1++;
ans[ans1].x=b[i].z;
ans[ans1].y=b[Rf[getgo(pos(b[i].x,b[i].y))]].ans;
}
sort(ans+
1,ans+ans1+
1,cmp2);
printf(
"%d\n",ans1);
for (i=
1;i<=ans1;i++)
printf(
"%d %d\n",ans[i].x,ans[i].y);
return 0;
}
(⊙v⊙)
关键点: 1.把网格按高度从大到小排序 由于要求最小值的最大值,又可以通过单个网格来更新答案; 所以可以采用排序的方法。
转载请注明原文地址: https://ju.6miu.com/read-500191.html