题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4746
先离散化所有坐标，然后对于每个镜子，行和列连一条双向边，跑最短路，最后对于目标位置的行和列取 $min$ 。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include<bits/stdc++.h> #define maxn 100010 #define pb push_back #define inf INT_MAX/2 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct point{ int x,y; point(int xx=0,int yy=0){x=xx,y=yy;} }p[maxn]; int n,xa,ya,xb,yb,tot; int dis[maxn*2],val[maxn*2]; vector<int>go[maxn*2]; queue<int>q; bool vis[maxn*2]; inline int find(int x){ return lower_bound(val+1,val+tot+1,x)-val; } inline void init(){ n=rd();xa=rd();ya=rd()+1000000000;xb=rd();yb=rd()+1000000000; val[++tot]=xa; val[++tot]=ya; val[++tot]=xb; val[++tot]=yb; for(int i=1; i<=n; i++){ p[i].x=rd(),p[i].y=rd()+1000000000; val[++tot]=p[i].x; val[++tot]=p[i].y; } sort(val+1,val+tot+1); tot=unique(val+1,val+tot+1)-val-1; xa=find(xa); ya=find(ya); xb=find(xb); yb=find(yb); for(int i=1; i<=n; i++){ p[i].x=find(p[i].x); p[i].y=find(p[i].y); } } inline void dijkstra(){ fill(dis+1,dis+tot+1,inf); dis[xa]=dis[ya]=0; q.push(xa); q.push(ya); while(!q.empty()){ int now=q.front(); q.pop(); if(vis[now])continue; vis[now]=true; for(int i=0; i<go[now].size(); i++){ int to=go[now][i]; if(dis[to]>dis[now]+1){ dis[to]=dis[now]+1; q.push(to); } } } } inline void work(){ for(int i=1; i<=n; i++){ go[p[i].x].pb(p[i].y); go[p[i].y].pb(p[i].x); } dijkstra(); if(min(dis[xb],dis[yb])>=inf)puts("-1"); else printf("%d\n",min(dis[xb],dis[yb])); } int main(){ init(); work(); return 0; } |