Smallest path from corner to corner of a 2D array

user_14399345 0
Viewed 189

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.

breadth-first-search queue algorithm java
1 Answers

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

user_94371580
Related