grid.py

class Solution:
    def __init__(self) -> None:
        # count: 3
        grid1 = [
            [0, 0, 1, 1, 0],
            [0, 1, 1, 1, 1],
            [0, 0, 0, 0, 0],
            [1, 1, 1, 1, 1],
            [0, 0, 0, 0, 0],
            [0, 1, 1, 0, 0]
        ]

        # count: 2
        grid2 = [
            [0, 0, 1, 1, 0],
            [0, 1, 1, 1, 1],
            [0, 0, 0, 0, 0],
            [1, 1, 1, 1, 1],
        ]
        
        # count: 4
        grid3 = [
            [0, 0, 1, 0, 0],
            [1, 0, 1, 0, 1],
            [0, 0, 0, 0, 0],
            [1, 1, 1, 0, 0],
        ]
        
        # count: 9
        grid4 = [
            [0, 0, 1, 0, 0, 0, 0, 1],
            [1, 0, 1, 0, 1, 0, 1, 0],
            [0, 0, 0, 0, 0, 1, 0, 0],
            [1, 1, 1, 0, 1, 0, 0, 1],
        ]
        
        self.grids = [grid1, grid2, grid3, grid4]
        
    
    def solution(self, grid):
        row, col = len(grid), len(grid[0])
        visited = [[-1] * col for _ in range(row)]
        
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    visited[i][j] = 0
        
        def dfs(grid, i, j):
            if visited[i][j] == 1: return
            row, col = len(grid), len(grid[0])
            # check its neighbors
            neighbors = []
            if i - 1 >= 0 and grid[i-1][j] == 1:
                neighbors.append((i-1, j))
            if i + 1 <= row -1 and grid[i+1][j] == 1:
                neighbors.append((i+1, j))
            if j - 1 >= 0 and grid[i][j-1] == 1:
                neighbors.append((i, j-1))
            if j + 1 <= col - 1 and grid[i][j+1] == 1:
                neighbors.append((i, j+1))             
            
            visited[i][j] = 1
            for (ni, nj) in neighbors:
                dfs(grid, ni, nj)

        count = 0
        for i in range(row):
            for j in range(col):
                if visited[i][j] == 0: # not visited
                    dfs(grid, i, j)
                    count += 1
        return count


if __name__ == '__main__':
    s = Solution()
    for grid in s.grids:
        count = s.solution(grid)
        print(f'counts: {count}')