Finding the maximum square sub | Python 3 program to find maximum K such that K x K is a submatrix with equal elements . ; Returns size of the largest square sub - matrix with all same elements . ; If elements is at top row or first column , it wont form a square matrix 's bottom-right ; Check if adjacent elements are equal ; If not equal , then it will form a 1 x1 submatrix ; Update result at each ( i , j ) ; Driver Code
Row = 6 NEW_LINE Col = 6 NEW_LINE def largestKSubmatrix ( a ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( Row ) ] for y in range ( Col ) ] NEW_LINE result = 0 NEW_LINE for i in range ( Row ) : NEW_LINE INDENT for j in range ( Col ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT if ( a [ i ] [ j ] == a [ i - 1 ] [ j ] and a [ i ] [ j ] == a [ i ] [ j - 1 ] and a [ i ] [ j ] == a [ i - 1 ] [ j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) , dp [ i - 1 ] [ j - 1 ] ) + 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT DEDENT result = max ( result , dp [ i ] [ j ] ) NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT a = [ [ 2 , 2 , 3 , 3 , 4 , 4 ] , [ 5 , 5 , 7 , 7 , 7 , 4 ] , [ 1 , 2 , 7 , 7 , 7 , 4 ] , [ 4 , 4 , 7 , 7 , 7 , 4 ] , [ 5 , 5 , 5 , 1 , 2 , 7 ] , [ 8 , 7 , 9 , 4 , 4 , 4 ] ] ; NEW_LINE print ( largestKSubmatrix ( a ) ) NEW_LINE