一道經典的 bfs 題。

提醒：本題解是為小白專做的，不想看的大佬請離開。

這道題首先一看就知道是 bfs，但是數據點不讓我們過： $1\le H,W\le 10^9$。

那么我們就需要優化了，從哪兒下手呢？看數據點第三行：$1\le N\le 10^5$。

圖很大，但是石頭不多，那么我們就可以從石頭下手。這里需要我們把思維方式轉換過來一下。

正常的 bfs 是去找路，那我們就找石頭！那石頭在哪兒呢？

首先，我們不可能在 bfs 的時候把所有的石頭全掃一遍然后找，這樣很明顯會 TLE。而我們再回憶一下 bfs 的過程：上下左右全走一遍，然后……

對啊！bfs 只掃這個點的這一行、這一列，我們為什么不能把每一行、每一列的石頭所在的列數、行數保存下來呢？但還是有個問題：如果我要跑一行的數據，很有可能會被數據點卡，怎么再優化呢？這就要請出查詢時間復雜度最低的算法了：二分！

總時間復雜度：最差情況下 $O(n{\log }_2(n))$。

代碼實現：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t,x,y,stx,sty,edx,edy;
map<pair<int,int>,int>dis;
map<int,set<int>>h,l;
queue<pair<int,int>>q;
void add(int u,int v,int now) {if(dis.find(make_pair(u,v))==dis.end()) {dis[make_pair(u,v)]=now;q.push(make_pair(u,v));}
}
signed main() {cin>>n>>m>>t>>stx>>sty>>edx>>edy;while(t--) {cin>>x>>y;h[x].insert(y);//保存行和列l[y].insert(x);}dis[make_pair(stx,sty)]=0;q.push(make_pair(stx,sty));while(!q.empty()) {pair<int,int>p=q.front();q.pop();int u=p.first,v=p.second;int now=dis[make_pair(u,v)];if(u==edx&&v==edy) {cout<<now;return 0;}auto it=h[u].lower_bound(v);//二分if(it!=h[u].end()) {add(u,(*it)-1,now+1);//這里我試過把函數中的部分放下來，但就是不知道為什么會錯}if(it!=h[u].begin()) {add(u,(*(--it))+1,now+1);}it=l[v].lower_bound(u);if(it!=l[v].end()) {add((*it)-1,v,now+1);}if(it!=l[v].begin()) {add((*(--it))+1,v,now+1);}}cout<<"-1";return 0;
}