Minimum odd cost path in a matrix | Python3 program to find Minimum odd cost path in a matrix ; Function to find the minimum cost ; leftmost element ; rightmost element ; Any element except leftmost and rightmost element of a row is reachable from direct upper or left upper or right upper row 's block ; Counting the minimum cost ; Find the minimum cost ; Driver code
M = 100 NEW_LINE N = 100 NEW_LINE def find_min_odd_cost ( given , m , n ) : NEW_LINE INDENT floor = [ [ 0 for i in range ( M ) ] for i in range ( N ) ] NEW_LINE min_odd_cost = 0 NEW_LINE i , j , temp = 0 , 0 , 0 NEW_LINE for j in range ( n ) : NEW_LINE INDENT floor [ 0 ] [ j ] = given [ 0 ] [ j ] NEW_LINE DEDENT for i in range ( 1 , m ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT floor [ i ] [ j ] = given [ i ] [ j ] ; NEW_LINE floor [ i ] [ j ] += min ( floor [ i - 1 ] [ j ] , floor [ i - 1 ] [ j + 1 ] ) NEW_LINE DEDENT elif ( j == n - 1 ) : NEW_LINE INDENT floor [ i ] [ j ] = given [ i ] [ j ] ; NEW_LINE floor [ i ] [ j ] += min ( floor [ i - 1 ] [ j ] , floor [ i - 1 ] [ j - 1 ] ) NEW_LINE DEDENT else : NEW_LINE INDENT temp = min ( floor [ i - 1 ] [ j ] , floor [ i - 1 ] [ j - 1 ] ) NEW_LINE temp = min ( temp , floor [ i - 1 ] [ j + 1 ] ) NEW_LINE floor [ i ] [ j ] = given [ i ] [ j ] + temp NEW_LINE DEDENT DEDENT DEDENT min_odd_cost = 10 ** 9 NEW_LINE for j in range ( n ) : NEW_LINE INDENT if ( floor [ n - 1 ] [ j ] % 2 == 1 ) : NEW_LINE INDENT if ( min_odd_cost > floor [ n - 1 ] [ j ] ) : NEW_LINE INDENT min_odd_cost = floor [ n - 1 ] [ j ] NEW_LINE DEDENT DEDENT DEDENT if ( min_odd_cost == - 10 ** 9 ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT return min_odd_cost NEW_LINE DEDENT m , n = 5 , 5 NEW_LINE given = [ [ 1 , 2 , 3 , 4 , 6 ] , [ 1 , 2 , 3 , 4 , 5 ] , [ 1 , 2 , 3 , 4 , 5 ] , [ 1 , 2 , 3 , 4 , 5 ] , [ 100 , 2 , 3 , 4 , 5 ] ] NEW_LINE print ( " Minimum ▁ odd ▁ cost ▁ is " , find_min_odd_cost ( given , m , n ) ) NEW_LINE