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

## A super nice problem needs several technologies to solve

3 min readAug 8

--

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

- 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²) - 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. - 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.