Connected Cells in a Grid

  • + 0 comments
    def connectedCell(matrix):
        def dfs(matrix, visited, i, j):
            # Stack for DFS
            stack = [(i, j)]
            count = 0
    
            while stack:
                x, y = stack.pop()
                if not (0 <= x < n and 0 <= y < m) or visited[x][y] or matrix[x][y] == 0:
                    continue
    
                visited[x][y] = True
                count += 1
    
                # Check all 8 possible directions
                for dx, dy in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
                    stack.append((x + dx, y + dy))
    
            return count
    
        n = len(matrix)
        m = len(matrix[0])
        visited = [[False] * m for _ in range(n)]
        max_region = 0
    
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 1 and not visited[i][j]:
                    size_of_region = dfs(matrix, visited, i, j)
                    max_region = max(max_region, size_of_region)
    
        return max_region