Minimum cost path in a Matrix by moving only on value difference of X | Python3 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
MAX = 1e18 NEW_LINE v = [ [ 0 , 0 ] ] * ( 151 ) NEW_LINE dp = [ [ - 1 for i in range ( 151 ) ] for i in range ( 151 ) ] NEW_LINE def min_operation ( i , j , val , x ) : NEW_LINE INDENT if ( i == n - 1 and j == m - 1 ) : NEW_LINE INDENT if ( val > v [ i ] [ j ] ) : NEW_LINE INDENT dp [ i ] [ j ] = MAX NEW_LINE return MAX NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = v [ i ] [ j ] - val NEW_LINE return dp [ i ] [ j ] NEW_LINE DEDENT DEDENT if ( i == n or j == m ) : NEW_LINE INDENT dp [ i ] [ j ] = MAX NEW_LINE return MAX NEW_LINE DEDENT if ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] NEW_LINE DEDENT if ( val > v [ i ] [ j ] ) : NEW_LINE INDENT dp [ i ] [ j ] = MAX NEW_LINE return MAX NEW_LINE DEDENT tmp = v [ i ] [ j ] - val NEW_LINE tmp += min ( min_operation ( i + 1 , j , val + x , x ) , min_operation ( i , j + 1 , val + x , x ) ) NEW_LINE dp [ i ] [ j ] = tmp NEW_LINE return tmp NEW_LINE DEDENT def solve ( x ) : NEW_LINE INDENT ans = 10 ** 19 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT val = v [ i ] [ j ] - x * ( i + j ) NEW_LINE for ii in range ( 151 ) : NEW_LINE INDENT for jj in range ( 151 ) : NEW_LINE INDENT dp [ ii ] [ jj ] = - 1 NEW_LINE DEDENT DEDENT val = min_operation ( 0 , 0 , val , x ) NEW_LINE ans = min ( ans , val ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 2 NEW_LINE m = 2 NEW_LINE x = 3 NEW_LINE v [ 0 ] = [ 15 , 153 ] NEW_LINE v [ 1 ] = [ 135 , 17 ] NEW_LINE print ( solve ( x ) ) NEW_LINE DEDENT