# Untitled

unknown
plain_text
25 days ago
3.8 kB
3
Indexable
Never
```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;
}
};```