Caută
  • oanaunciuleanu

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.

32 afișare0 comentariu