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.
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
        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
8 Years
Discussion Span
Last Post by Salem

Does your algorithm work?

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.


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.


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


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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.