Question

Given an MxN matrix filled with

X's and O's, find the largest square containing only X's and return its area. If there are no Xs in the entire matrix print 0.Input

The first line of input will be containing two space-separated integers, denoting M and N.

The next M lines will contain N space-separated integers, denoting the elements of the matrix.

Output

The output should be a single line containing the area of the maximum square.

Answer 1

def max_square(matrix):
    M, N = len(matrix), len(matrix[0]),
    arr = [[0 for _ in range(N + 1)] for _ in range(M + 1)]
    side_length = 0

    for i in range(1, len(arr)):
        for j in range(1, len(arr[0])):
            if matrix[i - 1][j - 1] == "X":
                arr[i][j] = min(arr[i][j - 1], arr[i - 1][j], arr[i - 1][j - 1]) + 1
                side_length = max(side_length, arr[i][j])

    return side_length * side_length


def parse_matrix():
    M, N = map(int, input().split())
    matrix = [input().split() for _ in range(M)]
    return matrix


matrix = parse_matrix()
print(max_square(matrix))