目录

前言

题目

思路

代码

后记

前言

此题是校内模拟赛自己改编的，想看题解的可以走了。所以此题可以用来对分治和搜索的提高，大家大致看看题目与我的思路就好。

题目

题目描述

滑雪场可以看成M x N的网格状山地(1 <= M,N <= 500),每个网格是一个近似的平面，具有水平高度值在0 .. 1,000,000米的范围内。

某些网格被指定为关键网格。当两个相邻网格之间的高度差的绝对值不超过某个参数D时，就可以相互到达。相邻关系是指某个格子的东、西、南、北的格子。

显然，当D不断减小时，原本可以相互到达的相邻格子就不能到达了。

滑雪赛的组委会想知道，为了保证各个关键网格之间彼此连通，最小的D是多少？

输入

?第1行：2个整数M和N

接下来M行，每行N个整数，表示各网格的高度

接下来M行，每行N个0或者1，1表示关键网格

输出

?第1行：1个整数，表示最小的D

样例输入

3 5

20 21 18 99 5

19 22 20 16 26

18 17 40 60 80

1 0 0 0 1

0 0 0 0 0

0 0 0 0 1

样例输出

21

思路

我先来解释一下题意。上面的一坨是整个滑雪场的高度，下面那一坨是每个点是否重要。每个点之间高度差的绝对值只要小于d就可以相互之间抵达，题目要让我们求出一个最小的d值使得每个关键网格之间都可以相互抵达（这么一分析好像真的包含的有图的思想）。

说真的，此题我一看就知道可以用广搜加分治来做。（可能还有其他更加高级的说法，比如用图的思想来解决）我们可以这样想，我们可以从小到大枚举一个d值，再从一个重要的点出发进行广搜，用一个tot来表示我们已经到达了多少个重要网格，当再用一个impp来存储重要网格的数量,当tot=impp时，就说明可以到达。如果这个d值不行了，最终答案就是d-1。

但是，你觉得像我这样智慧的人会用枚举这种愚蠢的做法吗？没错，这里我们就可以用到2分，每次都2分这个d值，这样，时间复杂度就会大幅减少了。（如果你并不知道分治是什么，你可以试试枚举的做法）；

代码

#include

#include

#include

#include

#include

using namespace std;

#define LL long long

#define N 600

#define M 600

LL read() {

LL f=1,s=0;char a=getchar();

while(!(a>='0' && a<='9')) { if (a=='-') f=-1; a=getchar() ; }

while(a>='0' && a<='9') { s=s*10+a-'0'; a=getchar(); }

return f*s;

}

struct node {

LL x,y;

};

int dir[4][2]={{1,0},{0,1},{-1,-1}};

LL n,m,h[M][N],l,r,impp,X,Y;

bool imp[M][N];

LL abss(LL a) {

if(a<0)

return -a;

return a;

}

bool check (LL hh) {//进行广搜

bool book[N][M];

memset(book,sizeof(book));//先初始化book标记数组（标记这个点走没走过）

int tot=impp;//这里跟上述思路不一样，是从大往小减已经到达的重要点

queue q;

book[1][1]=1;

node G; G.x=X;G.y=Y;

if(imp[1][1]==1)

tot--;

q.push(G);//初始元素入队,Y是最后一个重要点的坐标，当然不是必须要求最后一个

while(!q.empty()) {

LL x=q.front().x,y=q.front().y;

for(int i=0;i<4;i++) {//广搜,dir为方向数组

LL tox=x+dir[i][0],toy=y+dir[i][1];

if(book[tox][toy]==1 || tox>n || tox<1 || toy>m || toy<1 || abss(h[x][y]-h[tox][toy])>hh)

continue;

book[tox][toy]=1;

node G;G.x=tox,G.y=toy;

if(imp[tox][toy]==1)

tot--;

q.push(G);

if(!tot)//判断是否可取

return 1;

}

q.pop();

}

if(!tot)

return 1;

return 0;

}

int main()

{

n=read();m=read();//读入

h[1][1]=read();

l=h[1][1];

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++) {

if(i==1&&j==1)

continue;

h[i][j]=read();

l=min(l,h[i][j]);

r=max(r,h[i][j]);

}

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++) {

imp[i][j]=read();

if(imp[i][j]==1) {

impp++;

X=i;

Y=j;

}

}

r=r-l,l=0;

LL mid;

while(l

mid=(l+r)/2;

if(check(mid))

r=mid;

else

l=mid+1;

}

mid=(l+r)/2;

cout<

return 0;

}

后记

此题我虽然再考试时很快就想到了正解，却没有认真读题，直接从第（1,1）个网格开始搜，导致只得了30分，非常遗憾。希望以后能吸取教训，以后多用点时间读题。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!