Minimum cost path in a Matrix by moving only on value difference of X | C ++ implementation to find the minimum number of operations required to move from ( 1 , 1 ) to ( N , M ) ; Function to find the minimum operations required to move to bottom - right cell of matrix ; Condition to check if the current cell is the bottom - right cell of the matrix ; Condition to check if the current cell is out of matrix ; Condition to check if the current indices is already computed ; Condition to check that the movement with the current value is not possible ; Recursive call to compute the number of operation required to compute the value ; Function to find the minimum number of operations required to reach the bottom - right cell ; Loop to iterate over every possible cell of the matrix ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; const long long MAX = 1e18 ; long long n , m ; vector < long long > v [ 151 ] ; long long dp [ 151 ] [ 151 ] ; long long min_operation ( long long i , long long j , long long val , long long x ) { if ( i == n - 1 && j == m - 1 ) { if ( val > v [ i ] [ j ] ) { return dp [ i ] [ j ] = MAX ; } else { return dp [ i ] [ j ] = v [ i ] [ j ] - val ; } } if ( i == n j == m ) { return dp [ i ] [ j ] = MAX ; } if ( dp [ i ] [ j ] != -1 ) { return dp [ i ] [ j ] ; } if ( val > v [ i ] [ j ] ) { return dp [ i ] [ j ] = MAX ; } long long tmp = v [ i ] [ j ] - val ; tmp += min ( min_operation ( i + 1 , j , val + x , x ) , min_operation ( i , j + 1 , val + x , x ) ) ; return dp [ i ] [ j ] = tmp ; } long long solve ( long long x ) { long long ans = INT64_MAX ; for ( long long i = 0 ; i < n ; i ++ ) { for ( long long j = 0 ; j < m ; j ++ ) { long long val = v [ i ] [ j ] - x * ( i + j ) ; memset ( dp , -1 , sizeof ( dp ) ) ; val = min_operation ( 0 , 0 , val , x ) ; ans = min ( ans , val ) ; } } return ans ; } int main ( ) { n = 2 , m = 2 ; long long x = 3 ; v [ 0 ] = { 15 , 153 } ; v [ 1 ] = { 135 , 17 } ; cout << solve ( x ) << endl ; return 0 ; }