Minimum cells to be flipped to get a 2 * 2 submatrix with equal elements | Python 3 implementation of the approach ; Function to return the minimum flips required such that the submatrix from mat [ i ] [ j ] to mat [ i + 1 ] [ j + 1 ] contains all equal elements ; Function to return the minimum number of slips required such that the matrix contains at least a single submatrix of size 2 * 2 with all equal elements ; To store the result ; For every submatrix of size 2 * 2 ; Update the count of flips required for the current submatrix ; Driver code
import sys NEW_LINE def minFlipsSub ( mat , i , j ) : NEW_LINE INDENT cnt0 = 0 NEW_LINE cnt1 = 0 NEW_LINE if ( mat [ i ] [ j ] == '1' ) : NEW_LINE INDENT cnt1 += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt0 += 1 NEW_LINE DEDENT if ( mat [ i ] [ j + 1 ] == '1' ) : NEW_LINE INDENT cnt1 += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt0 += 1 NEW_LINE DEDENT if ( mat [ i + 1 ] [ j ] == '1' ) : NEW_LINE INDENT cnt1 += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt0 += 1 NEW_LINE DEDENT if ( mat [ i + 1 ] [ j + 1 ] == '1' ) : NEW_LINE INDENT cnt1 += 1 NEW_LINE DEDENT else : NEW_LINE INDENT cnt0 += 1 NEW_LINE DEDENT return min ( cnt0 , cnt1 ) NEW_LINE DEDENT def minFlips ( mat , r , c ) : NEW_LINE INDENT res = sys . maxsize NEW_LINE for i in range ( r - 1 ) : NEW_LINE INDENT for j in range ( c - 1 ) : NEW_LINE INDENT res = min ( res , minFlipsSub ( mat , i , j ) ) NEW_LINE DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ "0101" , "0101" , "0101" ] NEW_LINE r = len ( mat ) NEW_LINE c = len ( mat [ 0 ] ) NEW_LINE print ( minFlips ( mat , r , c ) ) NEW_LINE DEDENT