【力扣·每日一题】1036. 逃离大迷宫 (C++ bfs 思维)

【力扣·每日一题】1036. 逃离大迷宫 (C++ bfs 思维)

linkkk

题意

思路

常规最短路可以通过bfs解决，但是这个图的范围为 1 e 6 ∗ 1 e 6 1e6*1e6 1e6∗1e6，bfs的复杂度为 O ( 1 e 12 ) O(1e12) O(1e12)，会超时。
障碍的大小只有200个，从障碍入手考虑起点终点无法到达的情况就是起点被障碍包围或终点被障碍包围。
障碍斜着放包围的格子最多，为 n ∗ ( n − 1 ) / 2 n*(n-1)/2 n∗(n−1)/2个
所以如果从起点出发，经过的格子数大于这个的话说明起点没有被障碍包围。同理，终点也这样。
如果在过程中，就已经到达终点的话，那肯定也是可以的。
其余情况就说明了起点或终点被障碍包围了，为 f a l s e false false

代码

class Solution {
public:
    int nx[4]={0,0,1,-1};
    int ny[4]={1,-1,0,0};
    map,int>mp;
    int sum=0;
    bool isEscapePossible(vector>& blocked, vector& source, vector& target) {
        int x=blocked.size();
        for(int i=0;i,int>vis;
        int ans=0;
        queue>q;
        q.push({sx,sy});
        vis[{sx,sy}]=1;
        while(!q.empty()){
            ans++;
            pair 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<
                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;
    }
};