题意
思路
常规最短路可以通过bfs解决，但是这个图的范围为1 e 6 ∗ 1 e 6，bfs的复杂度为O ( 1 e 12 )，会超时。
障碍的大小只有200个，从障碍入手考虑起点终点无法到达的情况就是起点被障碍包围或终点被障碍包围。
障碍斜着放包围的格子最多，为n ∗ ( n − 1 ) / 2个
所以如果从起点出发，经过的格子数大于这个的话说明起点没有被障碍包围。同理，终点也这样。
如果在过程中，就已经到达终点的话，那肯定也是可以的。
其余情况就说明了起点或终点被障碍包围了，为f a l s e
代码
class Solution { public: int nx[4]={0,0,1,-1}; int ny[4]={1,-1,0,0}; map<pair<int,int>,int>mp; int sum=0; bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) { int x=blocked.size(); for(int i=0;i<x;i++) mp[{blocked[i][0],blocked[i][1]}]=1; sum=(x)*(x-1)/2; if(bfs(source[0],source[1],target[0],target[1])&&bfs(target[0],target[1],source[0],source[1])) return true; return false; } bool bfs(int sx,int sy,int ex,int ey){ map<pair<int,int>,int>vis; int ans=0; queue<pair<int,int>>q; q.push({sx,sy}); vis[{sx,sy}]=1; while(!q.empty()){ ans++; pair<int,int> now=q.front();q.pop(); if(now.first==ex&&now.second==ey){ // printf("(%d,%d)=>(%d,%d)\n",sx,sy,ex,ey); return true; } if(ans>sum){ // cout<<ans<<"==="<<sum<<endl; return true; } int x=now.first,y=now.second; for(int i=0;i<4;i++){ int xx=x+nx[i],yy=y+ny[i]; if(xx>=0&&xx<1000000&&yy>=0&&yy<1000000){ if(!mp.count({xx,yy})&&!vis.count({xx,yy})) vis[{xx,yy}]=1,q.push({xx,yy}); } } } return false; } }; /* */
