Last Day Where You Can Still Cross | Leetcode 1970

class Solution {
    struct DSU{
        vector<int> parent;
        DSU(int n) : parent(n,-1) {}
        int Find(int v) {
            if(parent[v] == -1)
                return v;
            return parent[v] = Find(parent[v]);
        }
        void Union(int u,int v){
            int p1 = Find(u);
            int p2 = Find(v);
            if(p1==p2)  return;

            parent[p1] = p2;
        }
    };
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        int n = row * col + 5;
        DSU dsu(n+5);
        int top_parent = n+1;
        int bottom_parent = n+2;

        vector<vector<bool>> land(row,vector<bool>(col,false));
        vector<int> dir = {-1,0,1,0,-1};

        for(int day=cells.size()-1;day>=0;--day){
            int r = cells[day][0]-1;
            int c = cells[day][1]-1;
            land[r][c] = true;

            int dsu_idx = r*col + c;
            if(r==0)        dsu.Union(dsu_idx,top_parent);
            if(r==row-1)    dsu.Union(dsu_idx,bottom_parent);

            for(int i=0;i<4;++i){
                int newR = r + dir[i];
                int newC = c + dir[i+1];
                if(newR<0 or newR>=row or newC<0 or newC>=col)
                    continue;

                if(land[newR][newC])
                    dsu.Union(dsu_idx,newR*col + newC);
            }
            if(dsu.Find(top_parent) == dsu.Find(bottom_parent))
                return day;
        }
        return 0;
    }
};
/*
//JAVA
class Solution {

    static class DSU {
        int[] parent;

        DSU(int n) {
            parent = new int[n];
            Arrays.fill(parent, -1);
        }

        int find(int v) {
            if (parent[v] == -1) return v;
            parent[v] = find(parent[v]);
            return parent[v];
        }

        void union(int u, int v) {
            int pu = find(u);
            int pv = find(v);
            if (pu == pv) return;
            parent[pu] = pv;
        }
    }

    public int latestDayToCross(int row, int col, int[][] cells) {

        int base = row * col + 5;
        DSU dsu = new DSU(base + 5);

        int TOP = base + 1;
        int BOTTOM = base + 2;

        boolean[][] land = new boolean[row][col];
        int[] dir = {-1, 0, 1, 0, -1};

        for (int day = cells.length - 1; day >= 0; day--) {

            int r = cells[day][0] - 1;
            int c = cells[day][1] - 1;
            land[r][c] = true;

            int id = r * col + c;

            if (r == 0) dsu.union(id, TOP);
            if (r == row - 1) dsu.union(id, BOTTOM);

            for (int i = 0; i < 4; i++) {
                int nr = r + dir[i];
                int nc = c + dir[i + 1];

                if (nr < 0 || nr >= row || nc < 0 || nc >= col)
                    continue;

                if (land[nr][nc]) {
                    dsu.union(id, nr * col + nc);
                }
            }

            if (dsu.find(TOP) == dsu.find(BOTTOM))
                return day;
        }
        return 0;
    }
}

#Python
class Solution:
    class DSU:
        def __init__(self, n):
            self.parent = [-1] * n

        def find(self, v):
            if self.parent[v] == -1:
                return v
            self.parent[v] = self.find(self.parent[v])
            return self.parent[v]

        def union(self, u, v):
            pu = self.find(u)
            pv = self.find(v)
            if pu == pv:
                return
            self.parent[pu] = pv

    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:

        base = row * col + 5
        dsu = self.DSU(base + 5)

        TOP = base + 1
        BOTTOM = base + 2

        land = [[False] * col for _ in range(row)]
        dir = [-1, 0, 1, 0, -1]

        for day in range(len(cells) - 1, -1, -1):
            r, c = cells[day]
            r -= 1
            c -= 1

            land[r][c] = True
            idx = r * col + c

            if r == 0:
                dsu.union(idx, TOP)
            if r == row - 1:
                dsu.union(idx, BOTTOM)

            for i in range(4):
                nr = r + dir[i]
                nc = c + dir[i + 1]

                if 0 <= nr < row and 0 <= nc < col and land[nr][nc]:
                    dsu.union(idx, nr * col + nc)

            if dsu.find(TOP) == dsu.find(BOTTOM):
                return day

        return 0
*/