Consider the following matrix:
Input: The entire list of coordinates ranging from (0,0) to (4,4).
A list indicating certain coordinates which cannot be used to generate a path reached.
- each position on the grid is a node
- nodes share an edge if exactly one coordinate differs by exactly 1
- X nodes (and their associated edges) are deleted
The problem then becomes, find the shortest path in the graph between two nodes. If the nodes are not in the same connected component, there is no such path.
Output: The shortest path between S and E, considering the positions of the X nodes, given by a sequence of coordinates.
So in the above picture, a possible route may be the following: (0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)->(4,3)->(4,4)
A total of eight steps.
If the Xs occur in a way that prevents any movement (i.e, Xs at (0,1),(1,1), and (1,0), it should return -1 or indicate in some other way no path is possible.)
I have received advice that the A* search algorithm (pseudocode in this link) is relevant to this problem, but I am having difficulty seeing how to apply it.