Skip to content

Instantly share code, notes, and snippets.

@marius92mc
Last active August 29, 2015 14:04
Show Gist options
  • Save marius92mc/2db5578e54d357dd5104 to your computer and use it in GitHub Desktop.
Save marius92mc/2db5578e54d357dd5104 to your computer and use it in GitHub Desktop.
Adjusted count from 0. Works fine.
/*
* =====================================================================================
*
* Filename: matrix_min_cost_path.cpp
*
* Description:
*
* Version: 1.0
* Created: 07/21/2014 02:23:53 PM
* Revision: none
* Compiler: gcc
*
* Author: YOUR NAME (),
* Organization:
*
* =====================================================================================
*/
#include <cstdio>
#define nmax 100
using namespace std;
int min(int a, int b, int c)
{
int min = a;
if (b < a)
min = b;
if (c < min)
return c;
return min;
}
int minIndex(int a, int b, int c)
{
int min = a;
if (b < a)
min = b;
if (c < min)
return 3; // c
if (min == a)
return 1; //a
return 2;
}
int minCostPath(int a[][nmax], int n, int m, int path[][nmax])
{
int dp[nmax][nmax];
dp[0][0] = a[0][0];
for (int i = 1; i < n; i++)
{
dp[i][0] = dp[i - 1][0] + a[i][0];
path[i][0] = 3;
}
for (int j = 1; j < m; j++)
{
dp[0][j] = dp[0][j - 1] + a[0][j];
path[0][j] = 1;
}
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
{
dp[i][j] = min(dp[i][j - 1],
dp[i - 1][j - 1],
dp[i - 1][j]) + a[i][j];
// saving the path
path[i][j] = minIndex(dp[i][j - 1],
dp[i - 1][j - 1],
dp[i - 1][j]);
}
return dp[n - 1][m - 1];
}
void viewPath(int i, int j, int path[][nmax], int a[][nmax])
{
if (path[i][j] != 0)
{
if (path[i][j] == 1)
viewPath(i, j - 1, path, a);
else
if (path[i][j] == 2)
viewPath(i - 1, j - 1, path, a);
else // path[i][j] == 3
viewPath(i - 1, j, path, a);
printf("%d ", a[i][j]);
}
else
printf("%d ", a[i][j]);
}
int main()
{
int n, m, a[nmax][nmax], path[nmax][nmax];
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
printf("%d\n", minCostPath(a, n, m, path));
viewPath(n - 1, m - 1, path, a);
return 0;
}
@marius92mc
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment