1254. Number of Closed Islands - Explanation

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        visit = set()

        def dfs(r, c):
            if r < 0 or c < 0 or r == ROWS or c == COLS:
                return 0  # False
            if grid[r][c] == 1 or (r, c) in visit:
                return 1  # True

            visit.add((r, c))
            res = True
            for dx, dy in directions:
                if not dfs(r + dx, c + dy):
                    res = False
            return res

        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                if not grid[r][c] and (r, c) not in visit:
                    res += dfs(r, c)

        return res

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [0, 1, 0, -1, 0]

        def dfs(r, c):
            if r < 0 or c < 0 or r == ROWS or c == COLS or grid[r][c] == 1:
                return
            grid[r][c] = 1
            for d in range(4):
                dfs(r + directions[d], c + directions[d + 1])

        for r in range(ROWS):
            dfs(r, 0)
            dfs(r, COLS - 1)
        for c in range(COLS):
            dfs(0, c)
            dfs(ROWS - 1, c)

        res = 0
        for r in range(1, ROWS - 1):
            for c in range(1, COLS - 1):
                if grid[r][c] == 0:
                    dfs(r, c)
                    res += 1
        return res

class Solution:
    def closedIsland(self, grid: list[list[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        visit = set()
        res = 0

        def bfs(r, c):
            q = deque([(r, c)])
            visit.add((r, c))
            is_closed = True

            while q:
                x, y = q.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if nx < 0 or ny < 0 or nx >= ROWS or ny >= COLS:
                        is_closed = False
                        continue
                    if grid[nx][ny] == 1 or (nx, ny) in visit:
                        continue
                    visit.add((nx, ny))
                    q.append((nx, ny))

            return is_closed

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 0 and (r, c) not in visit:
                    res += bfs(r, c)

        return res

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        N = ROWS * COLS
        def index(r, c):
            return r * COLS + c

        dsu = DSU(N)
        directions = [0, 1, 0, -1, 0]
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 0:
                    for d in range(4):
                        nr, nc = r + directions[d], c + directions[d + 1]
                        if min(nr, nc) < 0 or nr == ROWS or nc == COLS:
                            dsu.union(N, index(r, c))
                        elif grid[nr][nc] == 0:
                            dsu.union(index(r, c), index(nr, nc))

        res = 0
        rootN = dsu.find(N)
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    continue
                node = index(r, c)
                root = dsu.find(node)
                if root == node and root != rootN:
                    res += 1
        return res