My Mistakes

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;