-1

I wrote in an exam a backtracking code that moving between cell and counting paths, the conditions are if the next cell is i+k or j+k or i-k or j-k. the code somehow is still going out of bounds even due I tried to prevent it from doing so.

I tried adding fixing the code by adding +1 in the checking valid move in the "if" conditions. 

public class Test3
{
    public static int howManyPaths(int [][] mat)
    {
        return howManyPaths(mat,0,0,0);
    }

    private static int howManyPaths(int [][] mat, int i, int j, int count)
    {
        if(i == mat.length-1){return count;}
        if(j == mat[i].length-1){return howManyPaths(mat,i+1,0,count);}
        count = pathCount(mat,i,j);
        return howManyPaths(mat,i,j+1,count);
    }

    private static int pathCount(int [][] mat, int i, int j)
    {
        int k = mat[i][j];        
        if(i < mat.length-1 && mat[i][j] == mat[i+k][j] && i+k < mat.length-1){
            return 1 + pathCount(mat,i+k,j);}

        if(j < mat[i].length-1 && mat[i][j]==mat[i][j+k] && j+k < mat[i].length-1){
            return 1 + pathCount(mat,i,j+k);}

        if(i > 0 && mat[i][j]==mat[i-k][j] && i-k > 0){
            return 1 + pathCount(mat,i-k,j);}

        if(j > 0 && mat[i][j]==mat[i][j-k] && j-k > 0){
            return 1 + pathCount(mat,i,j-k);}
        return 1;
    }
}

the expected is how many paths and the actual results are "out of bounds".

Edited with the fixet code still not working

Alon Latman
  • 31
  • 8
  • 1
    First step: understand what a Out Of Bounds Exception is. Once you do, you'll know how to prevent it. – Zun Jul 28 '19 at 14:12
  • I suggest using a debugger to find out what's going wrong and where. Its probably going to be much quicker than us going through your code. – dumbPotato21 Jul 28 '19 at 14:24
  • I tried debugger and I do understand what is out of bounds exception is. – Alon Latman Jul 28 '19 at 14:33

1 Answers1

1

In your code, 

 if(i < mat.length-1 && mat[i][j] == mat[i+k][j]){
        return 1 + pathCount(mat,i+k,j);}

what will it be, if i+k>=mat.length? Or,

if(j < mat[i].length-1 && mat[i][j]==mat[i][j+k]+1){
        return 1 + pathCount(mat,i,j+k);

what will it be, if j+k>=mat[i].length? Or,

if(i > 0 && mat[i][j]==mat[i-k][j]){
        return 1 + pathCount(mat,i-k,j);}

what will it be, if i-k<0? Or,

if(j > 0 && mat[i][j]==mat[i][j-k]){
        return 1 + pathCount(mat,i,j-k);}

what will it be, if j-k<0?

Handle these cases as well. See, being i>0, still i-k can be less than or equal to 0. This is the trick in your case.

Hope you got it now.

Edit: After you editing your code still it is getting the same exception as you are accessing the indexes and then checking if the index is a valid one.

Not this: 

if(i < mat.length-1 && mat[i][j] == mat[i+k][j] && i+k < mat.length-1)

Instead, you must write:

if(i < mat.length-1 && i+k < mat.length-1 && mat[i][j] == mat[i+k][j])

Same for others as well.

By doing this, you will be able to get rid of java.lang.ArrayIndexOutOfBoundsException

Mukit09
  • 2,956
  • 3
  • 24
  • 44