Connected Cells in a Grid

  • + 0 comments

    Solution in Python3:

    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    #
    # Complete the 'connectedCell' function below.
    #
    # The function is expected to return an INTEGER.
    # The function accepts 2D_INTEGER_ARRAY matrix as parameter.
    #
    
    def connectedCell(matrix):
        # Write your code here
        ones = []
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 1:
                    ones.append((i, j))
        l = []
        while ones != []:
            one = ones.pop(0)
            ll = [one]
            m = 1
            n = 0
            while n != m:
                m = len(ll)
                for one in ll:
                    i, j = one[0], one[1]
                    neighbors = [(i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1)]
                    for neighbor in neighbors:
                        if neighbor in ones:
                            ones.remove(neighbor)
                            ll.append(neighbor)
                n = len(ll)
            l.append(len(ll))   
        return max(l)
    
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        n = int(input().strip())
    
        m = int(input().strip())
    
        matrix = []
    
        for _ in range(n):
            matrix.append(list(map(int, input().rstrip().split())))
    
        result = connectedCell(matrix)
    
        fptr.write(str(result) + '\n')
    
        fptr.close()