Untitled

class Solution {
public:
    // uncluttered code:
    bool bfs(vector<vector<int>>& grid, vector<vector<int>>& closest_thief, int lower_lim){
        int n=grid.size();
        if(closest_thief[0][0]<lower_lim || closest_thief[n-1][n-1]<lower_lim) return false;
        queue<pair<int,int>> q;
        q.push({0,0});
        int dir[]={0,1,0,-1,0};
        bool ans=false;
        vector<vector<int>> vis(n, vector<int>(n, 0));
        while(!q.empty()){
            auto pt=q.front();
            q.pop();
            vis[pt.first][pt.second]=1; // JUST RELYING ON THIS - WONT HELP COZ AFTER THE FIRST ORIGIN NODE, EACH OF THE FOUR NODES WILL ENTER THEIR NEIGHBOUR WHICH ARE MARKED VISITED  ONLY WHEN THEY WERE POPPED OUT OF QUEUE; HENCE TLE;
            for(int i=0;i<4;i++){
                if(pt.first+dir[i]<n and pt.first+dir[i]>=0 and pt.second+dir[i+1]<n and pt.second+dir[i+1]>=0 and closest_thief[pt.first+dir[i]][pt.second+dir[i+1]]>=lower_lim and vis[pt.first+dir[i]][pt.second+dir[i+1]]!=1){
                    if(pt.first+dir[i]==n-1 and pt.second+dir[i+1]==n-1) return true;
                    q.push({pt.first+dir[i], pt.second+dir[i+1]});
                    vis[pt.first+dir[i]][pt.second+dir[i+1]]=1; // PS: adding this line made it worked ie solved the initial TLE problem that by adding line 35, but it gives a new TLE for n=40 (tc 808);
                }
            }
        }
        return false;
    }// this is almost completely same as the solution in the editorial

    bool find_path_with_min_dist(vector<vector<int>>& grid, vector<vector<int>>& closest_thief, int lower_lim){
        return bfs(grid, closest_thief, lower_lim); 
    }
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n=grid.size();
        if(grid[0][0]==1 || grid[n-1][n-1]==1){
            return 0;
        }
        vector<vector<int>> closest_thief(n, vector<int>(n, 1e5));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    closest_thief[i][j]=0;
                    queue<vector<int>> q; // representing i,j,dist;
                    q.push({i,j,0});
                    vector<vector<int>> visited(n,vector<int> (n, 0));
                    int dir[]={0,1,0,-1,0};
                    while(!q.empty()){
                        auto it=q.front();
                        visited[it[0]][it[1]]=1;
                        q.pop();
                        for(int i=0;i<4;i++){
                            if(it[0]+dir[i]<n and it[0]+dir[i]>=0 and it[1]+dir[i+1]<n and it[1]+dir[i+1]>=0 and grid[it[0]+dir[i]][it[1]+dir[i+1]]!=1 and visited[it[0]+dir[i]][it[1]+dir[i+1]]!=1){
                                closest_thief[it[0]+dir[i]][it[1]+dir[i+1]]=min(closest_thief[it[0]+dir[i]][it[1]+dir[i+1]], it[2]+1);
                                q.push({it[0]+dir[i], it[1]+dir[i+1], it[2]+1});
                                visited[it[0]+dir[i]][it[1]+dir[i+1]]=1;
                            }
                        }
                    }
                }
            }
        }
        
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<n;j++){
        //         cout<<closest_thief[i][j]<<" ";
        //     }
        //     cout<<endl;
        // } // works fine;

        int ans;
        int start=0, end=n-1; //as dist can't be > n-1 anyway;
        while(start<=end){
            int mid=(start+end)/2;
            // cout<<"calling for mid = "<<mid<<endl;
            if(find_path_with_min_dist(grid, closest_thief, mid)){
                ans=mid;
                start=mid+1;
            }
            else{
                end=mid-1;
            }
        }
        return ans;
    }
};