2020第11届蓝桥杯国赛试题B:扩散( C++ / C )

大家好，我是3月份新人榜排名第三的 ༺Blog༒Hacker༻
支持我：点赞+收藏⭐️+留言
格言：༺永做优质༒programmer༻

⚜️我的更新时间会有所改变，每月2-4篇，感谢各位长期以来的支持！

⚜️题目描述
一个点每过一个单位时间就会向 4 4 4 个方向扩散一个距离，如图所示：两个点 a 、 b a、b a、b连通，记作 e ( a , b ) e(a,b) e(a,b)，当且仅当 a 、 b a、b a、b 的扩散区域有公共部分。

连通块的定义是块内的任意两个点 u 、 v u、v u、v都必定存在路径 e ( u , a 0 ) , e ( a 0 , a 1 ) , . . . , e ( a k , v ) e(u,a0),e(a0,a1),...,e(ak,v) e(u,a0),e(a0,a1),...,e(ak,v)。

给定平面上的 n n n 个点，问最早什么时候它们形成一个连通块?

⚜️输入格式
第一行一个数 n n n ，以下 n n n 行，每行一个点坐标。

⚜️输出格式
输出仅一个数，表示最早的时刻所有点形成连通块。

⚜️样例输入

2
0 0
5 5

⚜️样例输出

5

⚜️数据范围与提示
对于 20% 的数据，满足 1 ≤ n ≤ 5 , 1 ≤ X i , Y i ≤ 50 1≤n≤5,1≤X_i,Y_i≤50 1≤n≤5,1≤Xi​,Yi​≤50；
对于 100% 的数据，满足 1 ≤ n ≤ 50 , 1 ≤ X i , Y i ≤ 109 1≤n≤50,1≤X_i,Y_i≤109 1≤n≤50,1≤Xi​,Yi​≤109。
时间限制： 1 s 1s 1s
空间限制： 512 M B 512MB 512MB

#include
#define ll long long
#define MAXN 10005
using namespace std;
int n,m[MAXN][MAXN],a[MAXN];
struct node{
	int x,y;	
}k[MAXN];
void Manhattan() 
{
	for(int i=1;i
		for(int j=i+1;j<=n;++j) 
		{
			m[j][i]=m[i][j]=abs(k[i].x-k[j].x)+abs(k[i].y-k[j].y);
		}
	}
}
int check(ll s) 
{	
	int flor=0,sum=1,flag[MAXN]={ };
	a[1]=1;
	flag[1]=1;
	while(flor
		flor++;
		for(int i=1;i<=n;++i) 
		{
			if(flag[i]) 
			{
				continue;
			}
			if(m[a[flor]][i]<=2*s) 
			{
				flag[i]=1;
				a[++sum]=i;
			}
		}
	}
	return sum==n;
}
int main() 
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) 
	{
		scanf("%d %d",&k[i].x,&k[i].y);
	}
	Manhattan();
	int l=0,r=1000000005,mid;
	while(l<=r) 
	{
		mid=l+((r-l)/2);
		if(check(mid)) 
		{
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	printf("%d",l);
	return 0;
}