Recursion with 2 dimensional array

Question

I'm writing a recursive method to find all the possible paths in a two dimensional array. From the top left point (0,0) to the bottom right point last point. And returns the sums of the paths.

public static void printPathWeights(int[][] m)
{
    printPathWeights(m, 0, 0, 0);
}

public static void printPathWeights(int[][] m, int row, int col, int sum)
{
    if(row == 0 && col ==0)
    sum = 0;

    if (row == m.length - 1 && col == m[row].length - 1)
        System.out.println(sum);

    else
    {
        if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
        printPathWeights(m, row - 1, col, sum += m[row][col]); // Up
        if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
            printPathWeights(m, row + 1, col, sum += m[row][col]); // Down
        if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
            printPathWeights(m, row, col - 1, sum += m[row][col]); // Left
        if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
            printPathWeights(m, row, col + 1, sum += m[row][col]); // Right
    }
}

currently my problem is that this function get into endless loop and not print my sum

Whoever gave you that assignment might have been involved with last week's Hackerrank.com CodeSprint 5 contest. This is one of the problems they proposed :) — Miquel
– Miquel, Commented Jan 26, 2014 at 15:17

score 1 · Accepted Answer · 2014-01-26 15:58:08Z

1

I think it's getting stuck at:

if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
        printPathWeights(m, row, col - 1, sum += m[row][col]); // Left
if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
        printPathWeights(m, row, col + 1, sum += m[row][col]); // Right

It will perpetually keep jumping back and forth.

And, as Miquel pointed out, why can't the paths go up?

Solution: (Assuming paths may not cross themselves, otherwise the sum goes off to infinity)

Keep track of where you've been. Pass that history to the next recursion.
Add the value of the tile that you're on to the sum value that was passed as a parameter.
If you're at the finish, print the sum.
Else: Try to go in four possible directions. This will fail if there is no cell in that direction, IE you're at the edge. It will also fail if you've already been there.
If you can't move anywhere, IE you're stuck, you return without doing anything.

edited Jan 26, 2014 at 15:58

answered Jan 26, 2014 at 15:22

anon

Sign up to request clarification or add additional context in comments.

7 Comments

user2908206 Over a year ago

What i need to change in order to fix it ?

anon Over a year ago

I updated my answer with a solution. It might still have a few flaws, but it's a place to start.

user2908206 Over a year ago

If i am at the finish why return 1 ?

anon Over a year ago

Because you just found one more possible path. The caller method will add that one to the values returned by other directions and return that in turn.

user2908206 Over a year ago

i want to return the sum of the pass for example the path is in cells with values 1, 2, 4 so i need to return 7

|

Miquel · Accepted Answer · 2014-01-26 15:21:26Z

0

You'll need to mark cells as visited, or your algorithm will have you going left and right on the same row forever. Also, why can't you go up as well?

answered Jan 26, 2014 at 15:21

Miquel

15.7k8 gold badges56 silver badges88 bronze badges

Comments

Tony_M · Accepted Answer · 2014-03-31 12:45:21Z

public static void printPathWeights(int [][] m) 
 { 
printPathWeights (m, 0, 0, 0); 
 } 

 private static void printPathWeights(int [][]m, int i, int j,int sum) 
{ 
 if (i<0 || i>=m.length || j<0 || j>=m[0].length) 
 return; 
 if (m[i][j] == -1) 
 return; 
 if (i==m.length-1 && j==m[0].length-1) 
 System.out.println (sum + m[m.length-1][m[0].length-1]); 
 int temp = m[i][j]; 
 m[i][j] = -1; 
 printPathWeights (m, i+1, j, sum+temp); 
 printPathWeights (m, i, j+1, sum+temp); 
 printPathWeights (m, i-1, j, sum+temp); 
 printPathWeights (m, i, j-1, sum+temp); 
 m[i][j] = temp; 
  }

try this, you putting the -1 in a place you have already been earlier, and on fold you place back the numbers, and ready for the next paths

Yanivoff · Accepted Answer · 2014-08-24 21:21:22Z

Complete working code. Tested...

public static void printPathWeights(int [][] m) {

    printPathWeights( m, 0, 0, 0, 0 );

}

//1 - If Right cell is clear, 2 - If Left cell is clear, 0 - Neutral

private static int printPathWeights(int[][] m, int sum, int flag, int row, int col) {

    if ( row == m.length - 1 && col == m[0].length - 1 ){
        System.out.print( (sum + m[row][col]) + "  " );
        return sum;
    }

    //Check if the RIGHT cell legal - (That's to say current cell was not called by the rigth cell
    // and the boundry is legal)
    if( flag != 1 && ((col+1) <= m[0].length - 1) )
        printPathWeights( m, sum + m[row][col], 2, row, col + 1 );

    //Check if the DONN/Below cell is legal - (That is to say the boundry is legal. We do not check
    // if we came from below cell since we do not have 'UP' call)
    if( ((row+1) <= m.length - 1) )
        printPathWeights( m, sum + m[row][col], 0, row + 1, col ); 

    //Check if the LEFT cell legal - (That's to say current cell was not called by the LEFT cell
    // and the boundry is legal and if We are at the top level we DO NOT TURN LEFT)
    if( flag != 2 && ((col - 1) >= 0) && row != m.length - 1 )
        printPathWeights( m, sum + m[row][col], 1, row, col - 1 );

   return sum;

}

Collectives™ on Stack Overflow

Recursion with 2 dimensional array

4 Answers 4

7 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

7 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related