C# · 12月 20, 2021

C++滑雪场的高度差——一道分治与广搜的结合 提高分治与搜索

目录

前言

题目

思路

代码

后记

前言

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

题目

题目描述

滑雪场可以看成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 || toxm || toyhh)

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<r) {//进行二分

mid=(l+r)/2;

if(check(mid))

r=mid;

else

l=mid+1;

}

mid=(l+r)/2;

cout<<mid;//输出答案

return 0;

}

后记

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