CODEWITHSUNDEEP
javarecursion
user2908206
user2908206

Reputation: 265

Recursion with 2 dimensional array

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

Upvotes: 0

Views: 2966

Answers (4)

Yanivoff
Yanivoff

Reputation: 1

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;

}

Upvotes: 0

Tony_M
Tony_M

Reputation: 1

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

Upvotes: 0

Reinstate Monica
Reinstate Monica

Reputation: 2798

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.

Upvotes: 1

Miquel
Miquel

Reputation: 15675

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?

Upvotes: 0

Related Questions