DFS and Binary Search
4 min readAug 21, 2020
LeetCode 778 Swim in Rising Water
DFS and binary search together can solve some interesting problems.
778. Swim in Rising Water
class Solution {
public:
bool dfs(vector<vector<int>>& grid, int idx, int t, int N, unordered_set<int>& seen) {
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int i = idx/N, j = idx % N;
if (grid[i][j] > t) return false;
if (idx == N*N - 1) return true;
if (seen.count(idx)) return false;
else {
seen.insert(idx);
for (auto [di, dj] : dirs) {
auto r = i + di, c = j + dj;
if (r >= 0 && r < N && c >= 0 && c < N) {
int new_idx = r*N + c;
if (dfs(grid, new_idx, t, N, seen)) return true;
}
}
return false;
}
}
int swimInWater(vector<vector<int>>& grid) {
const int N = grid.size();
int lo = 0, hi = N * N - 1;
unordered_set<int> seen;
while (lo < hi) {
int mid = lo + (hi - lo)/2;
seen.clear();
bool good = dfs(grid, 0, mid, N, seen);
if (good) {
hi = mid;
}
else lo = mid + 1;
}
return lo;
}
};Using vector instead of set is much faster (from 120ms →32 ms)
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
class Solution {
public:
bool dfs(vector<vector<int>>& grid, vector<vector<int>>& seen, int i, int j, int t) {
auto N = grid.size();
seen[i][j] = 1;
if (grid[i][j] > t) return false;
if (i == N - 1 && j == N - 1) return true;
for (auto [di, dj] : dirs) {
auto r = i + di, c = j + dj;
if (r >= 0 && r < N &&
c >= 0 && c < N &&
grid[r][c] <= t && !seen[r][c]) {
if (grid[i][j] > t) return false;
if (dfs(grid, seen, r, c, t)) return true;
}
}
return false;
}
int swimInWater(vector<vector<int>>& grid) {
const int N = grid.size();
int lo = 0, hi = N * N - 1;
while (lo < hi) {
int mid = lo + (hi - lo)/2;
vector<vector<int>> seen(N, vector<int>(N, 0));
bool good = dfs(grid, seen, 0, 0, mid);
if (good) {
hi = mid;
}
else lo = mid + 1;
}
return lo;
}
};Using array and memset is even faster (32ms →28 ms)
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int seen[55][55];
class Solution {
public:
bool dfs(vector<vector<int>>& grid, int i, int j, int t) {
auto N = grid.size();
seen[i][j] = 1;
if (grid[i][j] > t) return false;
if (i == N - 1 && j == N - 1) return true;
for (auto [di, dj] : dirs) {
auto r = i + di, c = j + dj;
if (r >= 0 && r < N &&
c >= 0 && c < N &&
grid[r][c] <= t && !seen[r][c]) {
if (grid[i][j] > t) return false;
if (dfs(grid, r, c, t)) return true;
}
}
return false;
}
int swimInWater(vector<vector<int>>& grid) {
const int N = grid.size();
int lo = 0, hi = N * N - 1;
while (lo < hi) {
int mid = lo + (hi - lo)/2;
memset(seen, 0, sizeof seen);
bool good = dfs(grid, 0, 0, mid);
if (good) {
hi = mid;
}
else lo = mid + 1;
}
return lo;
}
};1631. Path With Minimum Effort
This is the third problem of LeetCode Weekly Contest 212.
BFS or DFS and binary search
int seen[200][200];
class Solution {
public:
bool good(vector<vector<int>>& a, int mid) {
int R = a.size(), C = a[0].size();
memset(seen, 0, sizeof(seen));
vector<pair<int, int>> openlist;
openlist.emplace_back(0, 0);
vector<pair<int, int>> dirs = {{0, 1},{1, 0},{0, -1},{-1, 0}};
seen[0][0] = 1;
while (!openlist.empty()) {
auto [i, j] = openlist.back(); openlist.pop_back();
for (auto [di, dj] : dirs) {
int r = i+di, c = j+dj;
if (r < 0 || r >= R || c < 0 || c >= C) {
continue;
}
if (seen[r][c]) continue;
if (abs(a[r][c] - a[i][j]) <= mid) {
if (r == R -1 && c == C - 1) {
return true;
}
seen[r][c] = 1;
openlist.emplace_back(r, c);
}
}
}
return false;
}
int minimumEffortPath(vector<vector<int>>& heights) {
int low = 2e6, high = -1;
const int R = heights.size(), C = heights[0].size();
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
low = min(low, heights[i][j]);
high = max(high, heights[i][j]);
}
}
int lo = 0, hi = high - low;
while (lo < hi) {
int mid = lo + (hi - lo)/2;
if (good(heights, mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
};Here is the code from Aoxiang Cui[2] for reference (BFS + binary search)
const int d4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};class Solution {
public:
int minimumEffortPath(vector<vector<int>>& a) {
int n = a.size(), m = a[0].size();
int low = 0, high = 1e6;
vector<bool> flag(n * m);
while (low != high) {
int mid = (low + high) / 2;
fill(flag.begin(), flag.end(), false);
flag[0] = true;
queue<int> Q;
Q.push(0);
while (!Q.empty()) {
int pos = Q.front();
Q.pop();
int x = pos / m, y = pos % m;
for (int k = 0; k < 4; ++k) {
int nx = x + d4[k][0];
int ny = y + d4[k][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (abs(a[nx][ny] - a[x][y]) > mid) continue;
int npos = nx * m + ny;
if (flag[npos]) continue;
flag[npos] = true;
Q.push(npos);
}
}
if (!flag[n * m - 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return high;
}
};
Thanks for reading.
The Dijkstra solution can be found in [1].
