Minimum changes required to make each path in a matrix palindrome | Function for counting changes ; Maximum distance possible is ( n - 1 + m - 1 ) ; Stores the maximum element ; Update the maximum ; Stores frequencies of values for respective distances ; Initialize frequencies of cells as 0 ; Count frequencies of cell values in the matrix ; Increment frequency of value at distance i + j ; Store the most frequent value at i - th distance from ( 0 , 0 ) and ( N - 1 , M - 1 ) ; Calculate max frequency and total cells at distance i ; Count changes required to convert all cells at i - th distance to most frequent value ; Driver code
def countChanges ( matrix , n , m ) : NEW_LINE INDENT dist = n + m - 1 NEW_LINE Max_element = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT Max_element = max ( Max_element , matrix [ i ] [ j ] ) NEW_LINE DEDENT DEDENT freq = [ [ 0 for i in range ( Max_element + 1 ) ] for j in range ( dist ) ] NEW_LINE for i in range ( dist ) : NEW_LINE INDENT for j in range ( Max_element + 1 ) : NEW_LINE INDENT freq [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT freq [ i + j ] [ matrix [ i ] [ j ] ] += 1 NEW_LINE DEDENT DEDENT min_changes_sum = 0 NEW_LINE for i in range ( dist // 2 ) : NEW_LINE INDENT maximum = 0 NEW_LINE total_values = 0 NEW_LINE for j in range ( Max_element + 1 ) : NEW_LINE INDENT maximum = max ( maximum , freq [ i ] [ j ] + freq [ n + m - 2 - i ] [ j ] ) NEW_LINE total_values += ( freq [ i ] [ j ] + freq [ n + m - 2 - i ] [ j ] ) NEW_LINE DEDENT min_changes_sum += total_values - maximum NEW_LINE DEDENT return min_changes_sum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 7 , 0 , 3 , 1 , 8 , 1 , 3 ] , [ 0 , 4 , 0 , 1 , 0 , 4 , 0 ] , [ 3 , 1 , 8 , 3 , 1 , 0 , 7 ] ] NEW_LINE minChanges = countChanges ( mat , 3 , 7 ) NEW_LINE print ( minChanges ) NEW_LINE DEDENT