Minimum odd cost path in a matrix
Given a matrix, the task is to find the cost of the minimum path which is odd to reach the bottom of a matrix. If no such path exists, print -1.
Note: Only right-bottom, left-bottom, and direct bottom moves are allowed.
Examples:
Input: mat[] =
{{ 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 }
Output: 11
Input: mat[][] =
{{1, 5, 2},
{7, 2, 2},
{2, 8, 1}}
Output: 5
Approach: This problem can be solved using dynamic programming:
For the first row (base case), the cost is
floor[0][j]=given[0][j] (floor is our cost array and given is our given matrix)// For most left elements
if(j==0)
floor[i][j]=given[i][j]+min(floor[i-1][j], floor[i-1][j+1]);// For rightmost element
else if(j == N-1)
floor[i][j] = given[i][j] + min(floor[i-1][j], floor[i-1][j-1])
- As any element except leftmost and rightmost is reachable from directly by the upper or left upper or right upper row’s block. So,
else
floor[i][j] = a[i][j] + min(floor[i-1][j-1] + floor[i-1][j] + floor[i-1][j+1])At last, return the minimum odd value from the last row. In case it is not present, return -1.
Below is the implementation of the above approach:
C++
// C++ program to find Minimum // odd cost path in a matrix#include <bits/stdc++.h>#define M 100 // number of rows#define N 100 // number of columnsusing namespace std;// Function to find the minimum costint find_min_odd_cost(int given[M][N], int m, int n){ int floor[M][N] = { { 0 }, { 0 } }; int min_odd_cost = 0; int i, j, temp; for (j = 0; j < n; j++) floor[0][j] = given[0][j]; for (i = 1; i < m; i++) for (j = 0; j < n; j++) { // leftmost element if (j == 0) { floor[i][j] = given[i][j]; floor[i][j] += min(floor[i - 1][j], floor[i - 1][j + 1]); } // rightmost element else if (j == n - 1) { floor[i][j] = given[i][j]; floor[i][j] += min(floor[i - 1][j], floor[i - 1][j - 1]); } // Any element except leftmost and rightmost element of a row // is reachable from direct upper or left upper or right upper // row's block else { // Counting the minimum cost temp = min(floor[i - 1][j], floor[i - 1][j - 1]); temp = min(temp, floor[i - 1][j + 1]); floor[i][j] = given[i][j] + temp; } } min_odd_cost = INT_MAX; // Find the minimum cost for (j = 0; j < n; j++) { if (floor[n - 1][j] % 2 == 1) { if (min_odd_cost > floor[n - 1][j]) min_odd_cost = floor[n - 1][j]; } } if (min_odd_cost == INT_MIN) return -1; return min_odd_cost;}// Driver codeint main(){ int m = 5, n = 5; int given[M][N] = { { 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 } }; cout << "Minimum odd cost is " << find_min_odd_cost(given, m, n); return 0;} |
Java
// Java program to find minimum odd // cost path in a matrixpublic class GFG { public static final int M = 100 ; public static final int N = 100 ; // Function to find the minimum cost static int find_min_odd_cost(int given[][], int m, int n) { int floor[][] = new int [M][N]; int min_odd_cost = 0; int i, j, temp; for (j = 0; j < n; j++) floor[0][j] = given[0][j]; for (i = 1; i < m; i++) for (j = 0; j < n; j++) { // leftmost element if (j == 0) { floor[i][j] = given[i][j]; floor[i][j] += Math.min(floor[i - 1][j], floor[i - 1][j + 1]); } // rightmost element else if (j == n - 1) { floor[i][j] = given[i][j]; floor[i][j] += Math.min(floor[i - 1][j], floor[i - 1][j - 1]); } // Any element except leftmost and rightmost element of a row // is reachable from direct upper or left upper or right upper // row's block else { // Counting the minimum cost temp = Math.min(floor[i - 1][j], floor[i - 1][j - 1]); temp = Math.min(temp, floor[i - 1][j + 1]); floor[i][j] = given[i][j] + temp; } } min_odd_cost = Integer.MAX_VALUE; // Find the minimum cost for (j = 0; j < n; j++) { if (floor[n - 1][j] % 2 == 1) { if (min_odd_cost > floor[n - 1][j]) min_odd_cost = floor[n - 1][j]; } } if (min_odd_cost == Integer.MIN_VALUE) return -1; return min_odd_cost; } // Driver code public static void main(String args[]) { int m = 5, n = 5; int 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 } }; System.out.println( "Minimum odd cost is " + find_min_odd_cost(given, m, n)); } // This Code is contributed by ANKITRAI1} |
Python3
# Python3 program to find Minimum # odd cost path in a matrixM = 100 # number of rowsN = 100 # number of columns# Function to find the minimum costdef find_min_odd_cost(given, m, n): floor = [[0 for i in range(M)] for i in range(N)] min_odd_cost = 0 i, j, temp = 0, 0, 0 for j in range(n): floor[0][j] = given[0][j] for i in range(1, m): for j in range(n): # leftmost element if (j == 0): floor[i][j] = given[i][j]; floor[i][j] += min(floor[i - 1][j], floor[i - 1][j + 1]) # rightmost element elif (j == n - 1): floor[i][j] = given[i][j]; floor[i][j] += min(floor[i - 1][j], floor[i - 1][j - 1]) # Any element except leftmost and rightmost # element of a row is reachable from direct # upper or left upper or right upper row's block else: # Counting the minimum cost temp = min(floor[i - 1][j], floor[i - 1][j - 1]) temp = min(temp, floor[i - 1][j + 1]) floor[i][j] = given[i][j] + temp min_odd_cost = 10**9 # Find the minimum cost for j in range(n): if (floor[n - 1][j] % 2 == 1): if (min_odd_cost > floor[n - 1][j]): min_odd_cost = floor[n - 1][j] if (min_odd_cost == -10**9): return -1; return min_odd_cost# Driver codem, n = 5, 5given = [[ 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 ]]print("Minimum odd cost is", find_min_odd_cost(given, m, n))# This code is contributed by mohit kumar |
C#
// C# program to find minimum odd // cost path in a matrixusing System;public class GFG { public static int M = 100 ; public static int N = 100 ; // Function to find the minimum cost static int find_min_odd_cost(int[,] given, int m, int n) { int[,] floor = new int [M,N]; int min_odd_cost = 0; int i, j, temp; for (j = 0; j < n; j++) floor[0,j] = given[0,j]; for (i = 1; i < m; i++) for (j = 0; j < n; j++) { // leftmost element if (j == 0) { floor[i,j] = given[i,j]; floor[i,j] += Math.Min(floor[i - 1,j], floor[i - 1,j + 1]); } // rightmost element else if (j == n - 1) { floor[i,j] = given[i,j]; floor[i,j] += Math.Min(floor[i - 1,j], floor[i - 1,j - 1]); } // Any element except leftmost and rightmost element of a row // is reachable from direct upper or left upper or right upper // row's block else { // Counting the minimum cost temp = Math.Min(floor[i - 1,j], floor[i - 1,j - 1]); temp = Math.Min(temp, floor[i - 1,j + 1]); floor[i,j] = given[i,j] + temp; } } min_odd_cost = int.MaxValue; // Find the minimum cost for (j = 0; j < n; j++) { if (floor[n - 1,j] % 2 == 1) { if (min_odd_cost > floor[n - 1,j]) min_odd_cost = floor[n - 1,j]; } } if (min_odd_cost == int.MinValue) return -1; return min_odd_cost; } // Driver code public static void Main() { int m = 5, n = 5; int[,] 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 } }; Console.Write( "Minimum odd cost is " + find_min_odd_cost(given, m, n)); } } |
PHP
<?php// PHP program to find Minimum // odd cost path in a matrix$M = 100; $N = 100;// Function to find the minimum costfunction find_min_odd_cost($given, $m, $n){ global $M, $N; $floor1[$M][$N] = array(array(0), array(0)); $min_odd_cost = 0; for ($j = 0; $j < $n; $j++) $floor1[0][$j] = $given[0][$j]; for ($i = 1; $i < $m; $i++) for ($j = 0; $j < $n; $j++) { // leftmost element if ($j == 0) { $floor1[$i][$j] = $given[$i][$j]; $floor1[$i][$j] += min($floor1[$i - 1][$j], $floor1[$i - 1][$j + 1]); } // rightmost element else if ($j == $n - 1) { $floor1[$i][$j] = $given[$i][$j]; $floor1[$i][$j] += min($floor1[$i - 1][$j], $floor1[$i - 1][$j - 1]); } // Any element except leftmost and rightmost // element of a row is reachable from direct // upper or left upper or right upper row's block else { // Counting the minimum cost $temp = min($floor1[$i - 1][$j], $floor1[$i - 1][$j - 1]); $temp = min($temp, $floor1[$i - 1][$j + 1]); $floor1[$i][$j] = $given[$i][$j] + $temp; } } $min_odd_cost = PHP_INT_MAX; // Find the minimum cost for ($j = 0; $j < $n; $j++) { if ($floor1[$n - 1][$j] % 2 == 1) { if ($min_odd_cost > $floor1[$n - 1][$j]) $min_odd_cost = $floor1[$n - 1][$j]; } } if ($min_odd_cost == PHP_INT_MIN) return -1; return $min_odd_cost;}// Driver code$m = 5; $n = 5;$given = array(array(1, 2, 3, 4, 6), array(1, 2, 3, 4, 5), array(1, 2, 3, 4, 5), array(1, 2, 3, 4, 5), array(100, 2, 3, 4, 5));echo "Minimum odd cost is " . find_min_odd_cost($given, $m, $n);// This code is contributed by Akanksha Rai?> |
Javascript
<script>// Javascript program to find minimum odd // cost path in a matrix let M = 100 ; let N = 100 ; // Function to find the minimum cost function find_min_odd_cost(given,m,n) { let floor = new Array(M); for(let i=0;i<M;i++) { floor[i]=new Array(N); for(let j=0;j<N;j++) { floor[i][j]=0; } } let min_odd_cost = 0; let i, j, temp; for (j = 0; j < n; j++) floor[0][j] = given[0][j]; for (i = 1; i < m; i++) for (j = 0; j < n; j++) { // leftmost element if (j == 0) { floor[i][j] = given[i][j]; floor[i][j] += Math.min(floor[i - 1][j], floor[i - 1][j + 1]); } // rightmost element else if (j == n - 1) { floor[i][j] = given[i][j]; floor[i][j] += Math.min(floor[i - 1][j], floor[i - 1][j - 1]); } // Any element except leftmost and rightmost element of a row // is reachable from direct upper or left upper or right upper // row's block else { // Counting the minimum cost temp = Math.min(floor[i - 1][j], floor[i - 1][j - 1]); temp = Math.min(temp, floor[i - 1][j + 1]); floor[i][j] = given[i][j] + temp; } } min_odd_cost = Number.MAX_VALUE; // Find the minimum cost for (j = 0; j < n; j++) { if (floor[n - 1][j] % 2 == 1) { if (min_odd_cost > floor[n - 1][j]) min_odd_cost = floor[n - 1][j]; } } if (min_odd_cost == Number.MIN_VALUE) return -1; return min_odd_cost; } // Driver code let m = 5, n = 5; let 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 ]]; document.write( "Minimum odd cost is " + find_min_odd_cost(given, m, n)); // This code is contributed by avanitrachhadiya2155</script> |
Output
Minimum odd cost is 11
Time Complexity: O(m * n)
Auxiliary Space: O(m * n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
