Connected Cells in a Grid

  • + 0 comments
    from collections import deque
    
    
    def connectedCell(matrix):
        visited = [[True if cell == 0 else False for cell in row] for row in matrix]
        max_num = 0
        
        r, c = len(matrix), len(matrix[0])
        directions = ((0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (1, -1), (-1, 1), (1, 1))
        
        for i in range(r):
            for j in range(c):
                if visited[i][j]:
                    continue
                    
                # filled cell found
                count = 0
                queue = deque([(i, j)])
                visited[i][j] = True
                while queue:
                    x, y = queue.popleft()
                    count += 1
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < r and 0 <= ny < c and not visited[nx][ny]:
                            queue.append((nx, ny))
                            visited[nx][ny] = True
                
                max_num = max(max_num, count)
                
        return max_num