Find Shortest path from source to destination in a matrix that satisfies given constraints

Given a N x N matrix of positive integers, find shortest path from the first cell of the matrix to its last cell that satisfies given constraints.


We can move exactly k steps from any cell in the matrix where k is the value of that cell. i.e. from any cell M[i][j] in the matrix M, we can move to location

M[i + M[i][j]][j] or M[i – M[i][j]][j] or M[i][j + M[i][j]] or M[i][j – M[i][j]].

Note that we are not allowed to make any diagonal moves.

 
For example,


Input:

[ 7  1  3  5  3  6  1  1  7  5 ]
[ 2  3  6  1  1  6  6  6  1  2 ]
[ 6  1  7  2  1  4  7  6  6  2 ]
[ 6  6  7  1  3  3  5  1  3  4 ]
[ 5  5  6  1  5  4  6  1  7  4 ]
[ 3  5  5  2  7  5  3  4  3  6 ]
[ 4  1  4  3  6  4  5  3  2  6 ]
[ 4  4  1  7  4  3  3  1  4  2 ]
[ 4  4  5  1  5  2  3  5  3  5 ]
[ 3  6  3  5  2  2  6  4  2  1 ]

Output:

Shortest Path length is 6
Shortest Path is: (0, 0) (0, 7) (0, 6) (1, 6) (7, 6) (7, 9) (9, 9)

 
Input:

[ 4  4  6  5  5  1  1  1  7  4 ]
[ 3  6  2  4  6  5  7  2  6  6 ]
[ 1  3  6  1  1  1  7  1  4  5 ]
[ 7  5  6  3  1  3  3  1  1  7 ]
[ 3  4  6  4  7  2  6  5  4  4 ]
[ 3  2  5  1  2  5  1  2  3  4 ]
[ 4  2  2  2  5  2  3  7  7  3 ]
[ 7  2  4  3  5  2  2  3  6  3 ]
[ 5  1  4  2  6  4  6  7  3  7 ]
[ 1  4  1  7  5  3  6  5  3  4 ]

Output:

Shortest Path length is 6
Shortest Path is: (0, 0) (0, 4) (5, 4) (5, 2) (5, 7) (5, 9) (9, 9)

 


 

We have already discussed a backtracking solution in previous post. The time complexity of above backtracking solution would be higher since all paths need to be traveled till destination is reached. However, since it is an shortest path problem, BFS would be an ideal choice. In this post, BFS solution is discussed.

Below is the complete algorithm –


1. Create an empty queue and enqueue source cell having
   distance 0 from source (itself) and mark it as visited

2. do till queue is not empty
   a) Pop front node from the queue
   b) If the popped node is destination node, then return its distance
   c) else for each of 4 adjacent cells of current cell, we enqueue each
      valid cell into the queue with +1 distance and mark them as visited

3. If all the nodes in the queue is processed and destination is not
   reached, then return false

 
Note that in BFS, all cells having shortest path as 1 are visited first, followed by their adjacent cells having shortest path as 1 + 1 = 2 and so on.. so if we reach any node in BFS, its shortest path = shortest path of parent + 1. So, the first occurrence of the destination cell gives us the result and we can stop our search there. It is not possible that the shortest path exists from some other cell for which we haven’t reached the given node yet. If any such path was possible, we would have already explored it.

Note that we can find all the possible locations we can move to from the given location by using the array that stores the relative position of movement from any location. For example, if the current location is (x, y), we can move to (x + row[k], y + col[k]) for 0 <= k < 4 using below array.

int row[] = { -1, 0, 0, 1 };
int col[] = { 0, -1, 1, 0 };

So, from position (x, y), we can move to:

(x – 1, y)
(x, y – 1)
(x, y + 1)
(x + 1, y)

 
C++ implementation –
 

Download   Run Code

Output:

Destination Found: (0, 0) (0, 4) (5, 4) (5, 2) (5, 7) (5, 9) (9, 9)
Shortest Path length is 6

 
The above program has huge space complexity as we’re storing complete path information for each node in the queue. Complexity can be improved and code can be simplified if we are asked to only find the shortest distance from sourcce to destination. Below is its C++ implementation –

 

Download   Run Code

Output:

Shortest Path length is 6

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz