Answer to Question #313099 in Python for psy

Question #313099

Area of Square

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.


Explanation

For example, if the given M, N and elements of matrix are as the following


4 5

X O X O O

X O X X X

X X O X X

X O O X O


The matrix from indices (1, 3) to (2, 4) has the maximum square with

X. So the output should be the area of the maximum rectangle with X, which is 4.

Sample Input 1

4 5

X O X O O

X O X X X

X X O X X

X O O X O

Sample Output 1

4

Sample Input 2

3 3

O X X

O X X

O O O

Sample Output 2

4



1
Expert's answer
2022-03-17T06:42:34-0400
def X_Only(Matrix:list):
    for row in Matrix:
        for cell in row:
            # check if value is not X
            if cell!='X':
                return False
    return True



def sub_size(lent:int):
    for start in range(lent):
        for stop in range(start+1, lent+1):
            yield(start, stop)




def squareAreaWithX(matr:list, M:int, N:int):
    maximum_area = 0
    for begin_x, stop_x in sub_size(M):
        for begin_y, stop_y in sub_size(N):
            temp_matrix = [i[begin_y:stop_y] for i in matr[begin_x:stop_x]]
            if X_Only(temp_matrix):
                x= stop_x-begin_x
                y= stop_y-begin_y
                if maximum_area < x*y:
                    maximum_area=x*y
    print(maximum_area)




while True:
    s = input()
    M, N = [int(i) for i in s.split()]
    matrix = list([] for i in range(N))
    for i in range(M):
        matrix[i]=list(input().split())
    #calculate area of the largest X matrix
    squareAreaWithX(matrix, M, N)

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS