Can you solve a problem by using all those technologies: BFS, DFS, Binary Search?

A super nice problem needs several technologies to solve

This was the 3rd problem of the weekly LC contest 357 (August 5, 2023). This is a super nice problem. I like it as it covers several impotant topics:

• BFS
• DFS
• Backtracking
• Binary Search

It is the first time, I found one problem can cover so many topics. If I am interviewing a strong candidate, I probably will ask him/her this question. Even if he/she can not have the solution immediately, I hope they can provide part of the code with some hints.

Problem

2812. Find the Safest Path in a Grid

Explanation

1. We want to know each cell’s closet 1. The naively solution will be O(n⁴) which is 400⁴, for sure TLE. However, if we think the problem reversely, we can use multiple source BFS to collect this info, which is only O(n²)
2. After that, actually, we can use backtrack to find all possible solutions, then pick up the optimal one. However, this one is too slow. I got TLE for this one during contest.
3. A better way is binary search and each time, we use a DFS to see whether can find a path from source to destination. Of course, you can also use BFS. By using this approach, the complexity is only O(n² log n), which is pretty fast.

My Code during the contest

typedef pair<int, int> PII;
vector<PII> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};
int memo[401][401];
int visited[401][401];
class Solution {
    public:
    int ret;
    void dfs(int i, int j, int n, int this_ret, vector<vector<int>>&visited){
        this_ret = min(this_ret, memo[i][j]);
        if (this_ret <= ret)return;
        if (i == n - 1 && j == n - 1) {
            ret = max(ret, this_ret);
            return;
        }
        for (auto [di, dj]: dirs){
            int r = i + di, c = j + dj;
            if ( r < 0 || r >= n || c < 0 || c >= n || visited[r][c])continue;
            visited[r][c] = 1;
            dfs(i + di, j + dj, n, this_ret, visited); 
            visited[r][c] = 0;
        }
    }

    bool good(int i, int j, int n, int mid){
        if (memo[n-1][n-1] < mid || memo[0][0] < mid)return false;
        if (i == n - 1 && j == n - 1) {
            if (memo[i][j] >= mid) return true;
            return false;
        }
        for (auto [di, dj]: dirs){
            int r = i + di, c = j + dj;
            if ( r < 0 || r >= n || c < 0 || c >= n || visited[r][c] || memo[r][c] < mid)continue;
            visited[r][c] = 1;
            if (good(r, c, n, mid)) return true; 
        }
        return false;

    }
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        const int n = grid.size();
        memset(memo, 0, sizeof memo);
        vector<vector<int>>seen(n, vector<int>(n, 0));
        vector<PII> Q;
        for (int i = 0; i < n;++i){
            for (int j = 0; j < n ;++j){
                if (grid[i][j] == 1){
                    Q.emplace_back(i, j);
                    seen[i][j] = 1;
                }
            }
        }
        // BFS
        int level = 1;
        while (!Q.empty()){
            vector<PII>new_Q;
            for (auto [i, j]: Q){
                for (auto [di, dj] : dirs){
                    int r = i + di, c = j + dj;
                    if (r < 0 || r >= n || c <0 || c >= n || seen[r][c])continue;
                    seen[r][c] = 1;
                    memo[r][c] = level;
                    new_Q.emplace_back(r, c);
                }
            }
            level ++;
            Q = new_Q;
        }
        int this_ret = memo[0][0];
        visited[0][0] = 1;
        ret = 0;
        int lo = 0, hi = 4*n;
        while (lo < hi){
            int mid = (lo + hi + 1) / 2;
            memset(visited, 0, sizeof visited);
            visited[0][0] = 1;
            if (good(0, 0, n, mid)){
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return lo;

    }
};

Thanks for reading.