# How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step

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.

So,

• 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.

• Welcome to CS.SE! I don't see a question here. We're a question-and-answer site, so we require you to articulate a specific, answerable question in your post. Also, we're not a coding site; we don't provide advice on implementation (though questions about algorithms are on-topic here); and we ask that you replace code with a concise description of ideas or pseudocode, as not everyone here knows Python. Also, please don't use images for text; that's not accessible and can't be found through search.
– D.W.
May 10, 2019 at 15:54
• Also, if you wanted to ask about an algorithm to solve some problem, we would need a specification of that problem (the input, the desired output, how the two relate). An example is not a substitute for a problem statement that defines what the output should be in all cases. If you can edit your question to address these points, I encourage you to do so.
– D.W.
May 10, 2019 at 15:55
• I've reframed the question in consideration of the above points. I have reattached the picture since I believe it gives clarity in describing the problem, and because there is nothing to be searched in this image. Let me know if I should address anything else. May 10, 2019 at 16:18