# DFS coordinates

The problem and the correct solution can be found HERE.

`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 (i < 0 || i >= N || j < 0 || j >= N) return false;        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) {                int new_idx = (i + di)*N + j + dj;                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();            if (dfs(grid, 0, mid, N, seen)) {                hi = mid;            }            else lo = mid + 1;        }        return lo;    }};`

The bug is in this line. I am not sure whether i+di, j+dj are valid or not. If they are not valid, we may generate valid new_idx and hence get wrong answer.

`int new_idx = (i + di)*N + j + dj;`

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

## Jimmy Shen

Data Scientist/MLE/SWE @takemobi