思路
- 先把所有跷跷板按照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;
}