0
$\begingroup$

Consider the following matrix:

enter image description here

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented May 10, 2019 at 15:54
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented May 10, 2019 at 15:55
  • $\begingroup$ 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. $\endgroup$
    – Richard K Yu
    Commented May 10, 2019 at 16:18

1 Answer 1

Reset to default
2
$\begingroup$

You're asking how to compute the shortest path between two vertices in a graph. Solution: use an algorithm for computing shortest paths. In your case, BFS would be a good choice. There's no need for A*.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.