📋 个人简介
🎉大家好，我是3月份新人榜排名第三的 ?Blog?Hacker?
💬支持我：点赞👍+收藏??+留言📝
🌺格言：?永做优质?programmer?
注（具体请见CF665B Shopping）:
??我的更新时间会有所改变，每月2-4篇，感谢各位长期以来的支持！
📣2020第11届蓝桥杯国赛试题B:扩散( C++ / C )
??题目描述
🌐一个点每过一个单位时间就会向
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
💯CODE
#include<bits/stdc++.h>
#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<n;++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<sum)
{
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;
}