# 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;    }};`