比赛 |
2025暑期集训第5场图论专场 |
评测结果 |
C |
题目名称 |
激光 |
最终得分 |
0 |
用户昵称 |
Hollow07 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2025-07-09 10:45:38 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+100;
ll n,xn,yn,xf,yf,jx[N],jy[N];
ll head[N],nxt[N],to[N],cnt;
ll dis[N];
bool check[N];
queue<ll> q;
void add(ll u,ll v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void spfa(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;check[1]=1;
q.push(1);
while(!q.empty()){
ll u=q.front();q.pop();
check[u]=0;
for (int i=head[u];i;i=nxt[i]){
ll v=to[i];
if (dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
if (!check[v]) {
q.push(v);
check[v] = 1;
}
}
}
}
}
int main(){
freopen("lasers.in","r",stdin);
freopen("lasers.out","w",stdout);
scanf("%lld %lld %lld %lld %lld",&n,&jx[1],&jy[1],&jx[n+2],&jy[n+2]);
for (int i=2;i<=n+1;i++){
scanf("%lld %lld",&jx[i],&jy[i]);
}
n+=2;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if (jx[i]==jx[j]||jy[i]==jy[j]){
add(i,j);add(j,i);
}
}
}
if (jx[1]==jx[n]||jy[1]==jy[n]){
printf("0");
return 0;
}
spfa();
if (dis[n]==0x3f3f3f3f3f3f3f3f) printf("-1");
else printf("%lld",dis[n]);
return 0;
}