Awesomeness!.py

"""
dfs.py
------

https://www.hackerrank.com/challenges/connected-cell-in-a-grid
09/22/16
"""


def get_neighbors(i, j):
    """Returns a list of matrix indices neighboring (i, j)."""
    return [(i - 1, j - 1), (i, j - 1), (i + 1, j - 1),
            (i - 1, j), (i + 1, j),
            (i - 1, j + 1), (i, j + 1), (i + 1, j + 1)]


def DFS(matrix, i, j, visited):
    """Perform DFS in matrix from the i,j cell, after having seen the cells in
    visited.

    Return a list of matrix indices that belong in the region.

    """
    value = matrix[i][j]
    if not value:
        return visited

    visited.append((i, j))

    for node in get_neighbors(i, j):
        if node not in visited:
            print('   following {},{}'.format(node[0], node[1]))
            # search modifies visited!
            DFS(matrix, node[0], node[1], visited)

    return visited


def largest_region():
    """Read the matrix, perform DFS, output the size of largest region."""
    # Read the matrix
    num_rows = int(input())
    num_cols = int(input())

    matrix = [[0] * num_cols for _ in range(num_rows)]
    for i in range(num_rows):
        matrix[i] = [int(s) for s in input().split(' ')]

    # Perform DFS
    region_sizes = []
    for i in range(1, num_rows):
        for j in range(1, num_cols):
            print('Starting at {},{}'.format(i, j))
            region = DFS(matrix, i, j, [])
            region_sizes.append(len(region))

    # Output the size of largest region
    return region_sizes


if __name__ == '__main__':
    print(largest_region())