Minimum changes required to make each path in a matrix palindrome | C ++ Program to implement the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  7 NEW_LINE int countChanges ( int matrix [ ] [ N ] , int n , int m ) { int dist = n + m - 1 ; int Max_element = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { Max_element = max ( Max_element , matrix [ i ] [ j ] ) ; } } int freq [ dist ] [ Max_element + 1 ] ; for ( int i = 0 ; i < dist ; i ++ ) { for ( int j = 0 ; j < Max_element + 1 ; j ++ ) freq [ i ] [ j ] = 0 ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { freq [ i + j ] [ matrix [ i ] [ j ] ] ++ ; } } int min_changes_sum = 0 ; for ( int i = 0 ; i < dist / 2 ; i ++ ) { int maximum = 0 ; int total_values = 0 ; for ( int j = 0 ; j < Max_element + 1 ; j ++ ) { maximum = max ( maximum , freq [ i ] [ j ] + freq [ n + m - 2 - i ] [ j ] ) ; total_values += freq [ i ] [ j ] + freq [ n + m - 2 - i ] [ j ] ; } min_changes_sum += total_values - maximum ; } return min_changes_sum ; } int main ( ) { int mat [ ] [ N ] = { { 7 , 0 , 3 , 1 , 8 , 1 , 3 } , { 0 , 4 , 0 , 1 , 0 , 4 , 0 } , { 3 , 1 , 8 , 3 , 1 , 0 , 7 } } ; int minChanges = countChanges ( mat , 3 , 7 ) ; cout << minChanges ; return 0 ; }