因为只有1e5个点，所以直接离散化bfs就好
#include <cstdio> #include <cstring> #include <queue> #include <set> #include <map> #include <stack> #include <cstdlib> #include <algorithm> #include <vector> #include <cmath> using namespace std; typedef long long LL; typedef pair<int,int>pii; const int N=1e5+5; const int INF=0x3f3f3f3f; const int mod=1000000007; pii p[N],tmp; int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]={-1,0,1,-1,1,-1,0,1}; int head[N],tot,d[N],cnt; struct Edge{ int v,next; }edge[8*N]; void add(int u,int v){ edge[tot].v=v; edge[tot].next=head[u]; head[u]=tot++; } queue<int>q; int get(int s,int t){ while(!q.empty())q.pop(); memset(d,-1,sizeof(d)); d[s]=0;q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); if(u==t)return d[t]; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(d[v]==-1)d[v]=d[u]+1,q.push(v); } } return -1; } int main(){ int x1,x2,y1,y2,n,s,t; while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){ scanf("%d",&n); memset(head,-1,sizeof(head)),cnt=tot=0; for(int i=1;i<=n;++i){ int x,l,r; scanf("%d%d%d",&x,&l,&r); for(int j=l;j<=r;++j) ++cnt,p[cnt].first=x,p[cnt].second=j; } sort(p+1,p+1+cnt); cnt=unique(p+1,p+1+cnt)-p-1; for(int i=1;i<=cnt;++i){ for(int j=0;j<8;++j){ tmp.first=p[i].first+dx[j]; tmp.second=p[i].second+dy[j]; int pos=lower_bound(p+1,p+1+cnt,tmp)-p; if(pos==cnt+1||p[pos].first!=tmp.first||p[pos].second!=tmp.second) continue; add(i,pos); } } tmp.first=x1,tmp.second=y1; s=lower_bound(p+1,p+1+cnt,tmp)-p; tmp.first=x2,tmp.second=y2; t=lower_bound(p+1,p+1+cnt,tmp)-p; printf("%d ",get(s,t)); } return 0; }