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

A super nice problem needs several technologies to solve

Jimmy (xiaoke) Shen
3 min readAug 8, 2023

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.

--

--

Jimmy (xiaoke) Shen
Jimmy (xiaoke) Shen

No responses yet