1970

Union Find solution
TC: O(r*c*An)

class UF{
private:
    vector<int> parent, rank;

public:
    UF(int n){
        parent.resize(n+1);
        for(int i=0; i<=n; i++)
            parent[i] = i;
        rank.resize(n+1, 0);
    }

    int find(int x){
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    void unionSet(int x, int y){
        int px = find(x);
        int py = find(y);
        if(px != py){
            if(rank[px] > rank[py]){
                parent[py] = px;
            }
            else{
                parent[px] = py;
                if(rank[px] == rank[py])
                    rank[py]++;
            }
        }
    }
};

class Solution {
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int n=(row+1)*(col+1);
        int grid[row+1][col+1];
        memset(grid, 0, sizeof grid);

        UF uf = UF(n);
        for(int i=1; i<col; i++){
            uf.unionSet(get_hash(1, i, col), get_hash(1, i+1, col));
            if(row > 1)
            uf.unionSet(get_hash(row, i, col), get_hash(row, i+1, col));
        }

        // Get the last state.
        int dx[4] = {1, 0, 0, -1};
        int dy[4] = {0, -1, 1, 0};
        for(auto vec: cells){
            grid[vec[0]][vec[1]] = 1;
        }

        // Make graph.
        for(int i=1; i<=row; i++){
            for(int j=1; j<=col; j++){
                if(grid[i][j]) continue;
                for(int k=0; k<4; k++){
                    int nextR = i+dx[k], nextC = j+dy[k];
                    if(valid(nextR, nextC, row, col) && grid[nextR][nextC] == 0){
                        if(i==1 && k==0)
                            uf.unionSet(get_hash(nextR, nextC, col), get_hash(i, j, col));
                        if(i != 1){
                            if(i==row && k==3){
                                uf.unionSet(get_hash(nextR, nextC, col), get_hash(i, j, col));
                            }
                            else if(i != row){
                                uf.unionSet(get_hash(nextR, nextC, col), get_hash(i, j, col));
                            }
                        }
                    }
                }
            }
        }

        int day = cells.size();
        int firstRowSet=0, lastRowSet=0;
        for(int i=1; i<=col; i++){
            if(grid[1][i] == 0) firstRowSet = 1;
            if(grid[row][i] == 0) lastRowSet = 1;
        }

        // Get the last day.
        while(day>0){
            if(firstRowSet && lastRowSet){
                int px = uf.find(get_hash(1,1,col));
                int py = uf.find(get_hash(row,1,col));
                if(px == py)
                    return day;
            }
            day--;
            int r=cells[day][0], c=cells[day][1];
            if(r == 1) firstRowSet = 1;
            if(r == row) lastRowSet = 1;
            grid[r][c] = 0;
            for(int k=0; k<4; k++){
                int nextR = r+dx[k], nextC = c+dy[k];
                if(valid(nextR, nextC, row, col) && grid[nextR][nextC] == 0){
                    uf.unionSet(get_hash(nextR, nextC, col), get_hash(r, c, col));
                }
            }
        }
        return 0;
    }

    int get_hash(int r, int c, int cols){
        return r*cols+c;
    }

    int valid(int r, int c, int row, int col){
        if(r>=1 && r<=row && c>=1 && c<=col) return true;
        return false;
    }

};

----------------------
Binary Search Solution
TC: O(r*c*logn)

class Solution {
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int left = 1, right = cells.size(), ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canWalk(cells, row, col, mid)) {
                ans = mid; // Update current answer so far
                left = mid + 1; // Try to find a larger day
            } else right = mid - 1; // Try to find a smaller day
        }
        return ans;
    }
    int DIR[5] = {0, 1, 0, -1, 0};
    bool canWalk(vector<vector<int>>& cells, int row, int col, int dayAt) {
        vector<vector<bool>> grid(row, vector<bool>(col, 0)); // Create grid in the `dayAt` th date
        for (int i = 0; i < dayAt; ++i) grid[cells[i][0]-1][cells[i][1]-1] = 1;
        queue<pair<int, int>> bfs;
        for (int c = 0; c < col; ++c) {
            if (grid[0][c] == 0) { // Add all valid start cells in the top row
                bfs.push({0, c});
                grid[0][c] = 1; // Mark as visited
            }
        }
        while (!bfs.empty()) {
            auto [r, c] = bfs.front(); bfs.pop();
            if (r == row - 1) return true; // Reach to bottom -> Return Valid
            for (int i = 0; i < 4; ++i) {
                int nr = r + DIR[i], nc = c + DIR[i+1];
                if (nr < 0 || nr == row || nc < 0 || nc == col || grid[nr][nc] == 1) continue;
                grid[nr][nc] = 1; // Mark as visited
                bfs.push({nr, nc});
            }
        }
        return false;
    }
};