牛牛与跷跷板

思路

• 先把所有跷跷板按照y坐标存起来，并按照左端点排序
• 然后建边
  1）左右连边
  枚举每行，左边的跷跷板的右端点与右边相邻的跷跷板的左端点相同，连边
  2）上下连边
  相邻两行，存在公共部分的连边
  这里可以采用枚举上方的跷跷板，然后找到第一个与它有公共部分的位置记为k，然后再向右找
  枚举到下一个时，需要把k回退一个，因为最后一个与上一个有公共部分，也会与下一个有公共部分
• 跑一边bfs得出答案

代码

// Problem: 牛牛与跷跷板
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9982/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

struct edge{
    int l,r,id;
};

int n;
vector<edge> row[N];
vector<int> g[N];

bool cmp(edge a,edge b){
    return a.l<b.l;
}

bool st[N];
int dis[N];

int bfs(){
    queue<int> q;
    q.push(1);st[1]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int v:g[u]){
            if(!st[v]){
                st[v]=1;
                dis[v]=dis[u]+1;
                if(v==n) return dis[n];
                q.push(v);
            }
        }
    }
    return dis[n];
}

void solve(){
    cin>>n;
    rep(i,1,n){
        int y,l,r;cin>>y>>l>>r;
        row[y].pb({l,r,i});
    }
    rep(i,0,1e5) sort(row[i].begin(),row[i].end(),cmp);
    rep(i,0,1e5){
        //左右连边
        for(int j=1;j<row[i].size();j++){
            if(row[i][j-1].r==row[i][j].l){
                int u=row[i][j-1].id,v=row[i][j].id;
                g[u].pb(v);g[v].pb(u);
            }
        }
        //上下连边
        int k=0;
        for(int j=0;j<row[i].size();j++){
            while(k<row[i+1].size()&&row[i][j].l>=row[i+1][k].r) k++;
            while(k<row[i+1].size()&&row[i][j].r>row[i+1][k].l){
                int u=row[i][j].id,v=row[i+1][k].id;
                g[u].pb(v);g[v].pb(u);
                k++;
            }
            k--;
        }
    }
    cout<<bfs()<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}