比赛 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;
}