Smallest path from corner to corner of a 2D array

I’m working on a problem where I’m trying to get from the top left corner, i.e. (0,0), to the bottom right, or (m – 1, n – 1), of an input m x n 2D array. Additionally, each element of the array represents what kind of jumps can be made from that square.

For example, a table that looks like:

1 2 1

1 1 1

1 1 1

Would have a minimum path of 3, since you can go from (0,0), jump 1 square right to (0,1), jump 2 squares down to (2, 1), then jump 1 square right to the destination of (2, 2).

My current implementation uses BFS, where I push each unvisited connected square into a queue, going through until I reach the corner or am unable to proceed; along the way, I update a seperate 2D array that contains the number of moves it takes to reach that particular coordinate on the actual board from the starting square.

My code works for many of the tests I throw at it, but for a few seemingly random test cases, it returns the wrong number of moves (higher than the actual number by quite a bit). I have no idea why this might be the case! Any suggestions on where I might have gone wrong would be really appreciated.

        Queue<int[]> queue = new LinkedList<>();
        int[][] distanceArray = new int[board.length][board[0].length];

//Add the initial starting coordinates to the queue
        queue.add(new int[]{0, 0});

        while(!queue.isEmpty()){

            int[] currentNode = queue.poll();
            int value = board[currentNode[0]][currentNode[1]];
// Check if the square has been visited before
            if(value != -1) {
//Get all adjacent squares from the current square (using the current square's jump value to get the new square coordinates)
                int[] north = {currentNode[0] - value, currentNode[1]};
                int[] south = {currentNode[0] + value, currentNode[1]};
                int[] east = {currentNode[0], currentNode[1] + value};
                int[] west = {currentNode[0], currentNode[1] - value};

//Set the current square to visited by marking it with -1
                board[currentNode[0]][currentNode[1]] = -1;

//Check each of the adjacent squares to see if fits within the perimeter of the board, updating the distance array and adding it to queue if it does
                if (north[0] >= 0 && board[north[0]][north[1]] != -1){
                    distanceArray[north[0]][north[1]] = distanceArray[currentNode[0]][currentNode[1]] + 1;

                    /*if(north[0] == board.length-1 && north[1] == board[0].length-1){
                        break;
                    }*/

                    queue.add(north);
                }

                if (south[0] < board.length && board[south[0]][south[1]] != -1){
                    distanceArray[south[0]][south[1]] = distanceArray[currentNode[0]][currentNode[1]] + 1;

                    /*if(south[0] == board.length-1 && south[1] == board[0].length-1){
                        break;
                    }*/

                    queue.add(south);
                }

                if (west[1] >= 0 && board[west[0]][west[1]] != -1){
                    distanceArray[west[0]][west[1]] = distanceArray[currentNode[0]][currentNode[1]] + 1;

                    /*if(west[0] == board.length-1 && west[1] == board[0].length -1){
                        break;
                    }*/

                    queue.add(west);
                }

                if (east[1] < board[0].length && board[east[0]][east[1]] != -1){
                    distanceArray[east[0]][east[1]] = distanceArray[currentNode[0]][currentNode[1]] + 1;
                    queue.add(east);

                    /*if(east[0] == board.length-1 && east[1] == board[0].length -1){
                        break;
                    }*/

                    queue.add(east);
                }



            }

        }

//return the bottom right corner value of the distance array, or -1 if it is still at 0
        if (distanceArray[board.length - 1][board[0].length - 1] == 0){
            return -1;
        }

        return distanceArray[board.length - 1][board[0].length - 1];

Answer

I think the problem is that you are updating the distanceArray without setting that square as visited (which normally would prevent overwriting that square in distanceArray), and only mark it as visited once that square reaches the top of the queue. This means that it’s possible for another path ahead in the queue to overwrite that distance before it gets marked as visited.

Here’s an example of this problem

Board:
1 1 1 1  
1 2 1 1  
1 1 1 1  
1 2 1 1  
Queue:   0,0 1,0 0,1 2,0 1,1 1,1 0,2 3,0 2,1 *3,1* 1,3 1,2 0,3 *3,1*   
Distance: 0   1   1   2   2   2   2   3   3   *3*   3   3   3   *4*  

As you can see visiting 1,1 enqueues 3,1 with distance 3, but then visiting 3,0 also enqueues 3,1 and overwrites its distance to 4, because 3,1 hasn’t reached the top of the queue and isn’t considered visited yet.

There are multiple ways of fixing this. The simplest is probably to just set it as visited as you enqueue it. However this isn’t quite viable in your exact situation since you use the board to mark visited. So instead you’ll probably want to store the visited information elsewhere. You could change the board squares from ints to an object that also holds their visited information as well as their step value (and while you’re at it add their shortest path distance).
Alternatively if you don’t want to rewrite a lot of your previous code you could just make another 2D array to store visited information, similar to your distanceArray.

You are also adding east to the queue twice. This shouldn’t cause any problems but is worth addressing anyways