1036. Escape a Large Maze

tag: BFS

Description

Solution

BFS + early quit.

Because 1M * 1M is too large for BFS, so we need to find a way to return quickly.

blocked.length <= 200 is a good quality we can look into. In a square, the best way to lock an area is laying all blocks 45° as following:

0th      _________________________
                        |O O O O O O O X
                        |O O O O O O X
                        |O O O O O X
                        |O O O O X
                        .O O O X
                        .O O X
                        .O X
                200th   |X

And there are maximally (199 + 1) * 199 /2 = 19900 grids. The exceeding of this number means we can not block one source. So we can return quickly by determine if 19901’s grid has been visited.

Code

class Solution {
    int dir[5] = {1, 0, -1, 0 , 1}; 
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        set<pair<int,int>> blocks;
        for(auto block : blocked)
            blocks.emplace(block[0],block[1]);
        return bfs(source, blocks, target) && bfs(target, blocks, source);
    }
    
    bool bfs(vector<int>& source, set<pair<int,int>> blocks, vector<int> &target){
        queue<pair<int,int>> q1;
        q1.emplace(source[0], source[1]);
        set<pair<int,int>> seen;
        seen.insert({source[0], source[1]});
        while(!q1.empty()){
            int size = q1.size();
            for(int i = 0; i < size; i ++){
                auto [r,c] = q1.front();
                q1.pop();
                for(int j = 1; j < 5; j++){
                    int x = r + dir[j-1], y = c + dir[j];
                    if(x >= 0 && x < 1E6 && y >= 0 && y < 1E6){
                        if(!seen.count({x,y}) && !blocks.count({x,y})){
                            if(x == target[0] && y == target[1])
                                return true;
                            q1.emplace(x,y);
                            seen.insert({x,y});
                        }
                    }
                }
            }
            if(seen.size() >= 19901){
                cout << "Oversized" << endl;
                return true;
            }
        }
        return false;
    }
};