C++ Binary Search + BFS Solution
\nclass Solution {\npublic:\n    vector<int> delx={-1,1,0,0};\n    vector<int> dely={0,0,-1,1};\n    bool check(int mid, vector<vector<int>>& dist){\n        in
```\nclass Solution {\npublic:\n    vector<int> delx={-1,1,0,0};\n    vector<int> dely={0,0,-1,1};\n    bool check(int mid, vector<vector<int>>& dist){\n        int n=dist.size();\n        if(dist[0][0]<mid or dist[n-1][n-1]<mid)return false;\n        vector<vector<bool>> vis(n,vector<bool>(n));\n        queue<pair<int,int>>q;q.push({0,0});vis[0][0]=true;\n        while(!q.empty()){\n            int size=q.size();\n            while(size--){\n                auto [i,j]=q.front();q.pop();\n                if(i==(n-1) and j==(n-1))return true;\n                for(int k=0;k<4;k++){\n                    int x=i+delx[k],y=j+dely[k];\n                    if(x>=0 and y>=0 and x<n and y<n and dist[x][y]>=mid and !vis[x][y]){\n                        vis[x][y]=true;\n                        q.push({x,y});\n                    }\n                }\n            }\n        }\n        return false;\n    }\n    int maximumSafenessFactor(vector<vector<int>>& grid) {\n        int n=grid.size();\n        if(grid[0][0] or grid[n-1][n-1])return 0;\n        queue<pair<int,int>>q;\n        vector<vector<int>> dist(n,vector<int>(n,-1));\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(grid[i][j]){\n                    q.push({i,j});\n                    dist[i][j]=0;\n                }\n            }\n        }\n        int level=1;\n        while(!q.empty()){\n            int size=q.size();\n            while(size--){\n                auto [i,j]=q.front();q.pop();\n                for(int k=0;k<4;k++){\n                    int x=i+delx[k],y=j+dely[k];\n                    if(x>=0 and y>=0 and x<n and y<n and dist[x][y]==-1){\n                        dist[x][y]=level;\n                        q.push({x,y});\n                    }\n                }\n            }\n            level++;\n        }\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                cout<<dist[i][j]<<" ";\n            }\n            cout<<endl;\n        }\n        int l=0,r=2*n;int ans=-1;\n        while(l<=r){\n            int mid=l+(r-l)/2;\n            if(check(mid,dist)){\n                l=mid+1;\n                ans=mid;\n            }else{\n                r=mid-1;\n            }\n        }\n        return ans;\n    }\n};\n```
['Breadth-First Search', 'Binary Tree']