大事な座標だけもって BFS. オブジェクトの周囲 4マスだけがグラフの頂点となる． map や upper_bound を使うので，遷移ごとに \(log(V)\) がかかる． ここで \(V\) は vertex の集合のサイズ． 前処理にもソートで \(log V\) が余分にかかる． 遷移しながらグラフを構成してる感じであって，前もってグラフを作る必要はない．
実装
遷移するとき，高速に障害物の位置を取得すれば十分． 今いる座標と同じ行(または列)に障害物があるか，あるならその直前の座標を取得したい． これは，\(x\) 座標に対して，障害物が座標 \( (x,y) \) にあるような \(y\) 全体を持っておけばよい． upper_bound を用いるので，あらかじめ座標の vector をソートしておく． \(x,y\) を入れ替えて同様のこともする．
メモ: {} で括ってスコープを作った． 行と列を入れ替えたときに，同じ変数名前を使い回したいから．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
// rem: vh は使わない
vll vh(2); cinv(vh);
ll n ; cin >> n;
vll s(2), g(2);
cinv(s);
cinv(g);
rep(i,n){
ll x,y; cin >> x >> y;
p[0][x].push_back(y);
p[1][y].push_back(x);
}
// rem: sort 必要 // upper_bound
rep(i,2){
for(auto [x,v]: p[i]){
sort(all(p[i][x]));
}
}
queue<pll> q;
map<pll,bool> vis;
map<pll,ll> dis;
auto push = [&](ll x, ll y, ll d) -> void {
if(vis[{x,y}]) return;
vis[{x,y}] = true;
q.push({x,y});
dis[{x,y}] = d;
};
push(s[0],s[1],0);
while(q.size()){
auto [x,y] = q.front(); q.pop();
ll d = dis[{x,y}];
{
vll *now = &(p[0][x]);
auto it = upper_bound(all(p[0][x]), y);// lower でも良い．常に今の場所が障害物と重なってないから．
if(it != (*now).end()) {
push(x, (*it)-1, d+1);
}
if(it != (*now).begin()){
it--;
push(x, (*it)+1, d+1);
}
}
{
vll *now = &(p[1][y]);
auto it = upper_bound(all(p[1][y]), x);// lower でも良い．常に今の場所が障害物と重なってないから．
if(it != (*now).end()) {
it--;
push((*it)+1, y, d+1);
}
}
}
ll ans = dis[{g[0],g[1]}];
if(!vis[{g[0], g[1]}]) ans = -1;
cout << ans << endl;
return 0;
}
*1:*it)-1, y, d+1);
}
if(it != (*now).begin(
