Problem: Connected Cells in a Grid (Python3)

Consider a matrix with n rows and m columns, where each cell contains either a 0 or a 1 and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally; in other words, cell [i][j]  is connected to cells [i-1][j-1], [i-1][j], [i-1][j+1], [i][j+1], [i+1][j+1], [i+1][j], [i+1][j-1], and [i][i-1], provided that the location exists in the matrix for that [i][j].

If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to zero or more cells in the region but is not necessarily directly connected to all the other cells in the region.

Task
Given an nxm matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.

Input Format

The first line contains an integer, n, denoting the number of rows in the matrix.
The second line contains an integer, m, denoting the number of columns in the matrix.
Each line i of the n subsequent lines contains m space-separated integers describing the respective values filling each row in the matrix.

Constraints

 0 < n,m < 10

Output Format

Print the number of cells in the largest region in the given matrix.

Sample Input

4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0

Sample Output

5

Explanation

The diagram below depicts two regions of the matrix; for each region, the component cells forming the region are marked with an X:

X X 0 0     1 1 0 0
0 X X 0     0 1 1 0
0 0 X 0     0 0 1 0
1 0 0 0     X 0 0 0

The first region has five cells and the second region has one cell. Because we want to print the number of cells in the largest region of the matrix, we print 5.

Approach:
Since the constrains are small, we can use brute-force algorithm. The hole algorithm can be described in three lines.

With each cell in the grid:
—- if it is 1 and not visited:
——– get all of it neighbors into a group (if any)

We need to implement the hard part. We need a groups list to store a list of groups (this is optional, you can use a list of group’s size), a collection to store visited cell (this should be set because in Python, O(1) is time complexity requires to check if a value in a set). We explore all 8 directions of a given cell, recursively call that method until we cant explore anymore. The algorithm has time complexity O(nxm), since we will never revisit a cell that is added into a group. Each cell is ensured to be visited only one.

 

EIGHT_DIRECTIONS = [
    (-1, -1),
    (-1, 0),
    (-1, 1),
    (0, 1),
    (1, 1),
    (1, 0),
    (1, -1),
    (0, -1)
]

def explore(grid, x, y, visited, groups):
    groups[-1].append((x, y))
    visited.add((x, y))
    for i, j in EIGHT_DIRECTIONS:
        next_x = x + i
        next_y = y + j
        if in_bound(grid, next_x, next_y) and \
           grid[next_x][next_y] == 1 and (next_x, next_y) not in visited:
           explore(grid, next_x, next_y, visited, groups)

def in_bound(grid, i, j):
    return i >= 0 and i < len(grid) and \
           j >= 0 and j < len(grid[0])

def connected_cells(grid, visited, groups):
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == 1 and (i,j) not in visited:
                groups.append(list())
                explore(grid, i, j, visited, groups)

def largest_region(groups):
    return max(len(group) for group in groups)

if __name__ == '__main__':
    n = int(input())
    m = int(input())
    grid = list()
    for i in range(n):
        line = input()
        grid.append([int(x) for x in line.strip().split()])
    groups = list()
    visited = set()
    connected_cells(grid, visited, groups)
    # for group in groups:
    #     print(group)
    print(largest_region(groups))