Count paths in a matrix

Question

This is a question from homework, that I got stuck with, and I'll be happy if someone could direct me.

A legal path is defined, by statring at the first cell (row 0 collumn 0), and countinue to the next step by adding the first and the second digits of the number in the cell, untill reaching the last cell (row n collumn n).

For example: If in cell [2][3] there is the number 15, then the next move can be: +1 in rows and +5 in collumns to [3][8] or +5 in row and +1 in collumns to [7][4]

The method should return how many legal paths are there.

I'm trying to use a backtracing recursive method for this problem, and I can't use any loops or any other method but overloading methods.

Here is the code I came up with so far:

public static int countPaths (int[][] mat)
{
    return countPaths(mat,0,0);
}

private static int countPaths(int[][] mat, int col, int row)
{


    if ((col==mat.length-1 && row==mat[0].length-1 )  {
        return 1;
    }    
    return countPaths(mat,mat[col][row]/10+col,mat[col][row]%10+row) + countPaths(mat,mat[col][row]%10-col,mat[col][row]/10-row);

} 

Thanks for any help !

Answer 1

If I understood the problem correctly, this is a solution.

public class MatrixPathCounter { private static int[][] mat = {{10,11,0},{10,11,10},{10,10,0}};

public static void main(String[] args)
{
    System.out.println(countPath(mat,0,0));
}

private static int countPath(int[][] mat, int x, int y)
{
    int n = mat.length -1;

    if (x==n && y==n)
        return 1;

    if(x>n || y>n)
        return 0;

    if(mat[x][y]==0)
        return 0;

    if(x+mat[x][y]/10 == x+mat[x][y]%10 && x+mat[x][y]%10 == x+mat[x][y]/10)
        return countPath(mat,x+mat[x][y]/10,y+mat[x][y]%10);
    else
        return countPath(mat,x+mat[x][y]/10,y+mat[x][y]%10) + countPath(mat,x+mat[x][y]%10,y+mat[x][y]/10 ); 
}

}