[C] Costo minimo

[magix2003]

CIao a tutti,
come esercizio all'uni mi hanno dato da scrivere un programma che cerchi il percorso minimo all'interno di una matrice. Il codice l'ho fatto, ora il problema è che vorrei inserire nel array cheapestR gli spostamenti effettuati dall'algoritmo inserendoci all'interno i valori della matrice. Lo so che questa probabilmente è la parte più semplice, ma sono in panne.

#include <stdio.h>
#include <stdlib.h>

#define n 5

int matrix[n][n] = {{7,3,5,6,1},
						  {1,6,8,0,2},
						  {3,5,7,9,2},
						  {7,6,1,1,4},
						  {5,7,4,8,2},
						 };
							
int cheapestR[n];

int min(int a, int b) {
	if (a <= b) {
		return a;
	} else {
		return b;
	}
}

int cheapestRec(int r, int c) {
	if (r == (n-1)) {
	   printf("\nRIGA: %d COLONNA: %d ELEMENTO: %d\n", r,c, matrix[r][c]);
	   return matrix[r][c];
	} else if (c == 0) {
	   printf("\nRIGA: %d COLONNA: %d ELEMENTO: %d\n", r,c, matrix[r][c]);
	   return matrix[r][c] + min(cheapestRec(r+1,c), cheapestRec(r+1,c+1));
	}else if (c == (n-1)) {
	   printf("\nRIGA: %d COLONNA: %d ELEMENTO: %d\n", r,c, matrix[r][c]);
	   return matrix[r][c] + min(cheapestRec(r+1,c), cheapestRec(r+1,c-1));
	} else {
	   printf("\nRIGA: %d COLONNA: %d ELEMENTO: %d\n", r,c, matrix[r][c]);
	   return matrix[r][c] + min(cheapestRec(r+1,c-1), min(cheapestRec(r+1,c), cheapestRec(r+1,c+1)));
	}
}

int start() {
   return min(cheapestRec(0,0),min(cheapestRec(0,1), min(cheapestRec(0,2),min(cheapestRec(0,3), cheapestRec(0,4)))));
}

int main() {
	print();
	printf("\n\nRESULT = %d\n",start());
	printPath();
	return 0;
}

Grazie

[magix2003]

UP