Min cost path in matrix

Here given code implementation process.

// C Program 
// Min cost path in matrix
#include <stdio.h>

#define R 4
#define C 5
// Returns the minimum of a given three values
int minValue(int a, int b, int c)
{
    if (a > b)
    {
        if (b > c)
        {
            return c;
        }
        else
        {
            return b;
        }
    }
    else
    {
        if (a > c)
        {
            return c;
        }
        else
        {
            return a;
        }
    }
}
// Find minimum cost path in given data matrix
void minCost(int data[R][C])
{
    // Auxiliary space which are used to find min path
    int dp[R][C];
    // Set first point
    dp[0][0] = data[0][0];
    // Loop controlling variables
    int i = 0;
    int j = 0;
    // Set first column
    for (i = 1; i < R; ++i)
    {
        dp[i][0] = data[i][0] + dp[i - 1][0];
    }
    // Set first row
    for (i = 1; i < C; ++i)
    {
        dp[0][i] = data[0][i] + dp[0][i - 1];
    }
    // iterate the loop through by row
    for (i = 1; i < R; ++i)
    {
        // iterate the loop through by column
        for (j = 1; j < C; ++j)
        {
            // minValue(top, top left, and left element)
            //  b   a
            //    ↖ ↑
            //  c ← x
            dp[i][j] = data[i][j] + minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]);
        }
    }
    // Display calculated result
    printf("\n Min Cost : %d", dp[R - 1][C - 1]);
}
int main()
{
    int data[R][C] = {
        {
            1 , 3 , 1 , 2 , 3
        },
        {
            2 , 1 , 1 , 2 , 8
        },
        {
            1 , 2 , 8 , 7 , 3
        },
        {
            1 , 2 , 3 , 2 , 5
        }
    };
    minCost(data);
    return 0;
}

Output

 Min Cost : 13
/*
  Java Program 
  Min cost path in matrix
*/
public class Cost{
	// Returns the minimum of a given three values
	public int minValue(int a, int b, int c)
	{
		if (a > b)
		{
			if (b > c)
			{
				return c;
			}
			else
			{
				return b;
			}
		}
		else
		{
			if (a > c)
			{
				return c;
			}
			else
			{
				return a;
			}
		}
	}
	// Find minimum cost path in given data matrix
	public void minCost(int[][] data, int r, int c)
	{
		// Auxiliary space which are used to find min path
		int[][] dp = new int[r][c];
		// Set first point
		dp[0][0] = data[0][0];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		// Set first column
		for (i = 1; i < r; ++i)
		{
			dp[i][0] = data[i][0] + dp[i - 1][0];
		}
		// Set first row
		for (i = 1; i < c; ++i)
		{
			dp[0][i] = data[0][i] + dp[0][i - 1];
		}
		// iterate the loop through by row
		for (i = 1; i < r; ++i)
		{
			// iterate the loop through by column
			for (j = 1; j < c; ++j)
			{
				// minValue(top, top left, and left element)
				//  b   a
				//    ↖ ↑
				//  c ← x
				dp[i][j] = data[i][j] + minValue(dp[i - 1][j], 
                                                 dp[i - 1][j - 1], 
                                                 dp[i][j - 1]);
			}
		}
		// Display calculated result
		System.out.print("\n Min Cost : " + dp[r - 1][c - 1]);
	}
    public static void main(String[] args)
    {
        Cost task = new Cost();
     
		int[][] data = 
		{
			{
				1 , 3 , 1 , 2 , 3
			} , 
			{
				2 , 1 , 1 , 2 , 8
			} , 
			{
				1 , 2 , 8 , 7 , 3
			} , 
			{
				1 , 2 , 3 , 2 , 5
			}
		};
		int r = data.length;
		int c = data[0].length;
		task.minCost(data,r,c);
    }
}

Output

 Min Cost : 13
// Include header file
#include <iostream>
#define R 4
#define C 5
using namespace std;
/*
  C++ Program 
  Min cost path in matrix
*/
class Cost
{
	public:
		// Returns the minimum of a given three values
		int minValue(int a, int b, int c)
		{
			if (a > b)
			{
				if (b > c)
				{
					return c;
				}
				else
				{
					return b;
				}
			}
			else
			{
				if (a > c)
				{
					return c;
				}
				else
				{
					return a;
				}
			}
		}
	// Find minimum cost path in given data matrix
	void minCost(int data[R][C])
	{
		// Auxiliary space which are used to find min path
		int dp[R][C];
		// Set first point
		dp[0][0] = data[0][0];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		// Set first column
		for (i = 1; i < R; ++i)
		{
			dp[i][0] = data[i][0] + dp[i - 1][0];
		}
		// Set first row
		for (i = 1; i < C; ++i)
		{
			dp[0][i] = data[0][i] + dp[0][i - 1];
		}
		// iterate the loop through by row
		for (i = 1; i < R; ++i)
		{
			// iterate the loop through by column
			for (j = 1; j < C; ++j)
			{
				// minValue(top, top left, and left element)
				//  b   a
				//    ↖ ↑
				//  c ← x
				dp[i][j] = data[i][j] + this->minValue(
                  dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]);
			}
		}
		// Display calculated result
		cout << "\n Min Cost : " << dp[R - 1][C - 1];
	}
};
int main()
{
	Cost task = Cost();
	int data[R][C] = {
		{
			1 , 3 , 1 , 2 , 3
		} , {
			2 , 1 , 1 , 2 , 8
		} , {
			1 , 2 , 8 , 7 , 3
		} , {
			1 , 2 , 3 , 2 , 5
		}
	};

	task.minCost(data);
	return 0;
}

Output

 Min Cost : 13
// Include namespace system
using System;
/*
  C# Program 
  Min cost path in matrix
*/
public class Cost
{
	// Returns the minimum of a given three values
	public int minValue(int a, int b, int c)
	{
		if (a > b)
		{
			if (b > c)
			{
				return c;
			}
			else
			{
				return b;
			}
		}
		else
		{
			if (a > c)
			{
				return c;
			}
			else
			{
				return a;
			}
		}
	}
	// Find minimum cost path in given data matrix
	public void minCost(int[,] data, int r, int c)
	{
		// Auxiliary space which are used to find min path
		int[,] dp = new int[r,c];
		// Set first point
		dp[0,0] = data[0,0];
		// Loop controlling variables
		int i = 0;
		int j = 0;
		// Set first column
		for (i = 1; i < r; ++i)
		{
			dp[i,0] = data[i,0] + dp[i - 1,0];
		}
		// Set first row
		for (i = 1; i < c; ++i)
		{
			dp[0,i] = data[0,i] + dp[0,i - 1];
		}
		// iterate the loop through by row
		for (i = 1; i < r; ++i)
		{
			// iterate the loop through by column
			for (j = 1; j < c; ++j)
			{
				// minValue(top, top left, and left element)
				//  b   a
				//    ↖ ↑
				//  c ← x
				dp[i,j] = data[i,j] + minValue(
                  dp[i - 1,j], dp[i - 1,j - 1], dp[i,j - 1]);
			}
		}
		// Display calculated result
		Console.Write("\n Min Cost : " + dp[r - 1,c - 1]);
	}
	public static void Main(String[] args)
	{
		Cost task = new Cost();
		int[,] data = {
			{
				1 , 3 , 1 , 2 , 3
			} , {
				2 , 1 , 1 , 2 , 8
			} , {
				1 , 2 , 8 , 7 , 3
			} , {
				1 , 2 , 3 , 2 , 5
			}
		};
		// Get number of row and column
		int r = data.GetLength(0);
		int c = data.GetLength(1);
		task.minCost(data, r, c);
	}
}

Output

 Min Cost : 13
<?php
/*
  Php Program 
  Min cost path in matrix
*/
class Cost
{
	// Returns the minimum of a given three values
	public	function minValue($a, $b, $c)
	{
		if ($a > $b)
		{
			if ($b > $c)
			{
				return $c;
			}
			else
			{
				return $b;
			}
		}
		else
		{
			if ($a > $c)
			{
				return $c;
			}
			else
			{
				return $a;
			}
		}
	}
	// Find minimum cost path in given data matrix
	public	function minCost( & $data, $r, $c)
	{
		// Auxiliary space which are used to find min path
		$dp = array_fill(0, $r, array_fill(0, $c, 0));
		// Set first point
		$dp[0][0] = $data[0][0];
		// Loop controlling variables
		$i = 0;
		$j = 0;
		// Set first column
		for ($i = 1; $i < $r; ++$i)
		{
			$dp[$i][0] = $data[$i][0] + $dp[$i - 1][0];
		}
		// Set first row
		for ($i = 1; $i < $c; ++$i)
		{
			$dp[0][$i] = $data[0][$i] + $dp[0][$i - 1];
		}
		// iterate the loop through by row
		for ($i = 1; $i < $r; ++$i)
		{
			// iterate the loop through by column
			for ($j = 1; $j < $c; ++$j)
			{
				// minValue(top, top left, and left element)
				//  b   a
				//    ↖ ↑
				//  c ← x
				$dp[$i][$j] = $data[$i][$j] + $this->minValue($dp[$i - 1][$j], $dp[$i - 1][$j - 1], $dp[$i][$j - 1]);
			}
		}
		// Display calculated result
		echo "\n Min Cost : ". $dp[$r - 1][$c - 1];
	}
}

function main()
{
	$task = new Cost();
	$data = array(
      array(1, 3, 1, 2, 3), 
      array(2, 1, 1, 2, 8), 
      array(1, 2, 8, 7, 3), 
      array(1, 2, 3, 2, 5)
    );
	// Get number of row and column
	$r = count($data);
	$c = count($data[0]);
	$task->minCost($data, $r, $c);
}
main();

Output

 Min Cost : 13
/*
  Node Js Program 
  Min cost path in matrix
*/
class Cost
{
	// Returns the minimum of a given three values
	minValue(a, b, c)
	{
		if (a > b)
		{
			if (b > c)
			{
				return c;
			}
			else
			{
				return b;
			}
		}
		else
		{
			if (a > c)
			{
				return c;
			}
			else
			{
				return a;
			}
		}
	}
	// Find minimum cost path in given data matrix
	minCost(data, r, c)
	{
		// Auxiliary space which are used to find min path
		var dp = Array(r).fill(0).map(() => new Array(c).fill(0));
		// Set first point
		dp[0][0] = data[0][0];
		// Loop controlling variables
		var i = 0;
		var j = 0;
		// Set first column
		for (i = 1; i < r; ++i)
		{
			dp[i][0] = data[i][0] + dp[i - 1][0];
		}
		// Set first row
		for (i = 1; i < c; ++i)
		{
			dp[0][i] = data[0][i] + dp[0][i - 1];
		}
		// iterate the loop through by row
		for (i = 1; i < r; ++i)
		{
			// iterate the loop through by column
			for (j = 1; j < c; ++j)
			{
				// minValue(top, top left, and left element)
				//  b   a
				//    ↖ ↑
				//  c ← x
				dp[i][j] = data[i][j] + this.minValue(
                  dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
                );
			}
		}
		// Display calculated result
		process.stdout.write("\n Min Cost : " + dp[r - 1][c - 1]);
	}
}

function main()
{
	var task = new Cost();
	var data = [
		[1, 3, 1, 2, 3] , 
        [2, 1, 1, 2, 8] , 
        [1, 2, 8, 7, 3] , 
        [1, 2, 3, 2, 5]
	];
	// Get number of row and column
	var r = data.length;
	var c = data[0].length;
	task.minCost(data, r, c);
}
main();

Output

 Min Cost : 13
#   Python 3 Program 
#   Min cost path in matrix

class Cost :
	#  Returns the minimum of a given three values
	def minValue(self, a, b, c) :
		if (a > b) :
			if (b > c) :
				return c
			else :
				return b
			
		else :
			if (a > c) :
				return c
			else :
				return a
			
		
	
	#  Find minimum cost path in given data matrix
	def minCost(self, data, r, c) :
		#  Auxiliary space which are used to find min path
		dp = [[0] * (c) for _ in range(r) ]
		#  Set first point
		dp[0][0] = data[0][0]
		#  Loop controlling variables
		i = 1
		j = 1
		#  Set first column
		while (i < r) :
			dp[i][0] = data[i][0] + dp[i - 1][0]
			i += 1
		
		i = 1
		#  Set first row
		while (i < c) :
			dp[0][i] = data[0][i] + dp[0][i - 1]
			i += 1
		
		i = 1
		#  iterate the loop through by row
		while (i < r) :
			#  iterate the loop through by column
			while (j < c) :
				#  minValue(top, top left, and left element)
				#   b   a
				#     ↖ ↑
				#   c ← x
				dp[i][j] = data[i][j] + self.minValue(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1])
				j += 1
			
			i += 1
			j = 1
		
		#  Display calculated result
		print("\n Min Cost : ", dp[r - 1][c - 1], end = "")
	

def main() :
	task = Cost()
	data = [
		[1, 3, 1, 2, 3] , 
        [2, 1, 1, 2, 8] , 
        [1, 2, 8, 7, 3] , 
        [1, 2, 3, 2, 5]
	]
	#  Get number of row and column
	r = len(data)
	c = len(data[0])
	task.minCost(data, r, c)

if __name__ == "__main__": main()

Output

 Min Cost :  13
#   Ruby Program 
#   Min cost path in matrix

class Cost 
	#  Returns the minimum of a given three values
	def minValue(a, b, c) 
		if (a > b) 
			if (b > c) 
				return c
			else 
				return b
			end

		else 
			if (a > c) 
				return c
			else 
				return a
			end

		end

	end

	#  Find minimum cost path in given data matrix
	def minCost(data, r, c) 
		#  Auxiliary space which are used to find min path
		dp = Array.new(r) {Array.new(c) {0}}
		#  Set first point
		dp[0][0] = data[0][0]
		#  Loop controlling variables
		i = 1
		j = 1
		#  Set first column
		while (i < r) 
			dp[i][0] = data[i][0] + dp[i - 1][0]
			i += 1
		end

		i = 1
		#  Set first row
		while (i < c) 
			dp[0][i] = data[0][i] + dp[0][i - 1]
			i += 1
		end

		i = 1
		#  iterate the loop through by row
		while (i < r) 
			#  iterate the loop through by column
			while (j < c) 
				#  minValue(top, top left, and left element)
				#   b   a
				#     ↖ ↑
				#   c ← x
				dp[i][j] = data[i][j] + self.minValue(
                  dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
                )
				j += 1
			end

			i += 1
			j = 1
		end

		#  Display calculated result
		print("\n Min Cost : ", dp[r - 1][c - 1])
	end

end

def main() 
	task = Cost.new()
	data = [
		[1, 3, 1, 2, 3] , 
        [2, 1, 1, 2, 8] , 
        [1, 2, 8, 7, 3] , 
        [1, 2, 3, 2, 5]
	]
	#  Get number of row and column
	r = data.length
	c = data[0].length
	task.minCost(data, r, c)
end

main()

Output

 Min Cost : 13
/*
  Scala Program 
  Min cost path in matrix
*/
class Cost
{
	// Returns the minimum of a given three values
	def minValue(a: Int, b: Int, c: Int): Int = {
		if (a > b)
		{
			if (b > c)
			{
				return c;
			}
			else
			{
				return b;
			}
		}
		else
		{
			if (a > c)
			{
				return c;
			}
			else
			{
				return a;
			}
		}
	}
	// Find minimum cost path in given data matrix
	def minCost(data: Array[Array[Int]], r: Int, c: Int): Unit = {
		// Auxiliary space which are used to find min path
		var dp: Array[Array[Int]] = Array.fill[Int](r, c)(0);
		// Set first point
		dp(0)(0) = data(0)(0);
		// Loop controlling variables
		var i: Int = 1;
		var j: Int = 1;
		// Set first column
		while (i < r)
		{
			dp(i)(0) = data(i)(0) + dp(i - 1)(0);
			i += 1;
		}
		i = 1;
		// Set first row
		while (i < c)
		{
			dp(0)(i) = data(0)(i) + dp(0)(i - 1);
			i += 1;
		}
		i = 1;
		// iterate the loop through by row
		while (i < r)
		{
			// iterate the loop through by column
			while (j < c)
			{
				// minValue(top, top left, and left element)
				//  b   a
				//    ↖ ↑
				//  c ← x
				dp(i)(j) = data(i)(j) + this.minValue(
                  dp(i - 1)(j), dp(i - 1)(j - 1), dp(i)(j - 1)
                );
				j += 1;
			}
			i += 1;
			j = 1;
		}
		// Display calculated result
		print("\n Min Cost : " + dp(r - 1)(c - 1));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Cost = new Cost();
		var data: Array[Array[Int]] = Array(
          Array(1, 3, 1, 2, 3), 
          Array(2, 1, 1, 2, 8), 
          Array(1, 2, 8, 7, 3), 
          Array(1, 2, 3, 2, 5)
        );
		// Get number of row and column
		var r: Int = data.length;
		var c: Int = data(0).length;
		task.minCost(data, r, c);
	}
}

Output

 Min Cost : 13
/*
  Swift 4 Program 
  Min cost path in matrix
*/
class Cost
{
	// Returns the minimum of a given three values
	func minValue(_ a: Int, _ b: Int, _ c: Int)->Int
	{
		if (a > b)
		{
			if (b > c)
			{
				return c;
			}
			else
			{
				return b;
			}
		}
		else
		{
			if (a > c)
			{
				return c;
			}
			else
			{
				return a;
			}
		}
	}
	// Find minimum cost path in given data matrix
	func minCost(_ data: [[Int]], _ r: Int, _ c: Int)
	{
		// Auxiliary space which are used to find min path
		var dp: [[Int]] = 
          Array(repeating: Array(repeating: 0, count: c), count: r);
		// Set first point
		dp[0][0] = data[0][0];
		// Loop controlling variables
		var i: Int = 1;
		var j: Int = 1;
		// Set first column
		while (i < r)
		{
			dp[i][0] = data[i][0] + dp[i - 1][0];
			i += 1;
		}
		i = 1;
		// Set first row
		while (i < c)
		{
			dp[0][i] = data[0][i] + dp[0][i - 1];
			i += 1;
		}
		i = 1;
		// iterate the loop through by row
		while (i < r)
		{
			// iterate the loop through by column
			while (j < c)
			{
				// minValue(top, top left, and left element)
				//  b   a
				//    ↖ ↑
				//  c ← x
				dp[i][j] = data[i][j] + self.minValue(
                  dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
                );
				j += 1;
			}
			i += 1;
			j = 1;
		}
		// Display calculated result
		print("\n Min Cost : ", dp[r - 1][c - 1], terminator: "");
	}
}
func main()
{
	let task: Cost = Cost();
	let data: [[Int]] = [
		[1, 3, 1, 2, 3] , 
        [2, 1, 1, 2, 8] , 
        [1, 2, 8, 7, 3] , 
        [1, 2, 3, 2, 5]
	];
	// Get number of row and column
	let r: Int = data.count;
	let c: Int = data[0].count;
	task.minCost(data, r, c);
}
main();

Output

 Min Cost :  13
/*
  Kotlin Program 
  Min cost path in matrix
*/
class Cost
{
	// Returns the minimum of a given three values
	fun minValue(a: Int, b: Int, c: Int): Int
	{
		if (a > b)
		{
			if (b > c)
			{
				return c;
			}
			else
			{
				return b;
			}
		}
		else
		{
			if (a > c)
			{
				return c;
			}
			else
			{
				return a;
			}
		}
	}
	// Find minimum cost path in given data matrix
	fun minCost(data: Array < Array < Int >> , r: Int, c: Int): Unit
	{
		// Auxiliary space which are used to find min path
		var dp: Array < Array < Int >> = Array(r)
		{
			Array(c)
			{
				0
			}
		};
		// Set first point
		dp[0][0] = data[0][0];
		// Loop controlling variables
		var i: Int = 1;
		var j: Int = 1;
		// Set first column
		while (i < r)
		{
			dp[i][0] = data[i][0] + dp[i - 1][0];
			i += 1;
		}
		i = 1;
		// Set first row
		while (i < c)
		{
			dp[0][i] = data[0][i] + dp[0][i - 1];
			i += 1;
		}
		i = 1;
		// iterate the loop through by row
		while (i < r)
		{
			// iterate the loop through by column
			while (j < c)
			{
				// minValue(top, top left, and left element)
				//  b   a
				//    ↖ ↑
				//  c ← x
				dp[i][j] = data[i][j] + this.minValue(
                  dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]
                );
				j += 1;
			}
			i += 1;
			j = 1;
		}
		// Display calculated result
		print("\n Min Cost : " + dp[r - 1][c - 1]);
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Cost = Cost();
	var data: Array < Array < Int >> = arrayOf(
      arrayOf(1, 3, 1, 2, 3), 
      arrayOf(2, 1, 1, 2, 8), 
      arrayOf(1, 2, 8, 7, 3), 
      arrayOf(1, 2, 3, 2, 5)
    );
	// Get number of row and column
	var r: Int = data.count();
	var c: Int = data[0].count();
	task.minCost(data, r, c);
}

Output

 Min Cost : 13
Trace the minimum path in matrix

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved