## bodom_lx

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
}
}
}``````

## Salem 5,138

I would say given the nature of the question and the material you've covered so far that a simple brute-force approach is perhaps what is wanted.

## bodom_lx

It works but not in the way I would like to make it working.
First of all, I don't know how could I store the paths discovered. I'm just able to print them, right now.

## Prabakar 77

it does choose some path. I doubt weather it will find all paths exhaustively. like
left, right forward in random order

## Salem 5,138

So you also pass
- something which records the 'path' so far. As you recurse, you append the current step, as you leave you remove the last path step.
- if you get to the end and the accumulated cost is <max, then print the path you accumulated.
- if the cost so far is already >= max, then go back a step.