top of page
Caută
  • Poza scriitoruluioanaunciuleanu

Minimum Cost Path in Matrix




In a matrix you have to find the minimum cost path to reach the last cell from the first one, meaning that starting from the top left cell you have to reach the bottom right cell by using the fastest route. You can only move down or right.



// Minimum Cost Path in Matrix
#include <iostream>
using namespace std;

#define X 5
#define Y 5


int minimumCostPathInMatrix(int matrix[X][Y], int x, int y)
{

	if (y == 0 || x == 0)
    {
        return INT_MAX;
    }

	if (x == 1 && y == 1)
    {
        return matrix[0][0];
    }

	return min(minimumCostPathInMatrix(matrix, x - 1, y), minimumCostPathInMatrix(matrix, x, y - 1)) + matrix[x - 1][y - 1];
}

int main()
{
	int matrix[X][Y] =
	{
		{ 9, 7, 4, 3, 2 },
		{ 5, 8, 6, 9, 8 },
		{ 7, 2, 1, 3, 8 },
		{ 9, 1, 2, 4, 6 },
		{ 2, 9, 7, 7, 3 }
	};

	int minCost = minimumCostPathInMatrix(matrix, X, Y);
	cout << "The minimum cost path in matrix is: " << minCost << "." << endl;
	return 0;
}

The minimum cost path in matrix is: 39.

52 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no overlapping, in order to obtain the maximum profit. Solution: 1. static

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed vertically 2 x 1 or horizontally as 1 x 2. Solution: 1. static

bottom of page