Thursday, January 28, 2016

Minimum cost path between two points in a matrix

#include <iostream>
using namespace std;

int min_num (int a , int b, int c) {

int m = a;

if (m > b) {
m = b;
}

if (m > c) {
m = c;
}

return m;
}

int minCost (int a[3][3] , int m, int n) {

int cost[m][n];

cost[0][0] = a[0][0];

for (int i = 1; i <= n ; i++) {
cost[0][i] = cost[0][i-1] + a[0][i];
}

for (int j = 1; j <= m; j++) {
cost[j][0] = cost[j-1][0] + a[j][0];
}

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cost[i][j] = a[i][j] + min_num (cost[i-1][j-1] , cost[i][j-1] ,cost[i-1][j]);
}
}

return cost[m][n];
}

int main() {
int cost[3][3] = { {1, 2, 3},
                      {4, 8, 2},
                      {1, 5, 3} };
    printf(" %d ", minCost(cost, 2, 2));
    return 0;
}

No comments: