Hi everybody, I've got a question for you. As assignment for the dsa course I've got a task regarding an array with cost values stored in each cell. The following is the array:
int C[5][5] = {
{8, 2, 3, 1, 5 },
{0, 6, 4, 9, 7 },
{6, 5, 8, 3, 4 },
{2, 7, 1, 9, 5 },
{6, 8, 3, 5, 1 }
};
Imagining this array as a checkerboard, I have to find a way to start from any element contained in the last row (6, 8, 3, 5, 1 ) and to arrive to the first row (8, 2, 3, 1, 5).
I can move either forward, or diagonally left or diagonally right. Each movement is associated a cost, represented by the number contained in the destination cell.
Example:
starting from C[4][2]=3, I may decide to move to C[3][1]=7 or to C[3][2]=1 or to C[3][3]=9
My algorithm, which has to be recursive, must calculate the cheapest path to the first row.
Any hints? Does a classic algorithm have anything to do with this problem? Would the Dijkstra algorithm help me? We haven't studied graphs yet.
I believe that the function should have the following schema:
void printPaths(int row, int col){
if(row==0){ // we reach the end of the array, return
return;
}else{
if(col>-1){ // to be sure that we don't exit the array
printPaths(row-1,col-1); // move diag-left
}
printPaths(row-1,col); // move forw
if(col<5){ // to be sure that we don't exit the array
printPaths(row-1,col+1); // move diag-right
}
}
}