Skip to main content
added 653 characters in body
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$. For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A*. The vertices are the grid points labelled "0". You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked 0). You can solve this with either BFS or A*: BFS is simpler to implement, A* will run faster.


If you additionally want to find the shortest path through all of the shapes (something that's not stated in the question), then you can fo the following: for all points $Q$ in shape $S_1$, and all points $R$ in shape $S_2$, calculate the shortest way to get from $Q$ to $R$ while avoiding shape $A$. Then add these as edges to a directed graph (where the length of the edge $Q\to R$ corresponds to the length of the shortest such path). Also add edges $R \to R'$ for each pair of points $R,R'$ in the same shape where you can enter the shape via $R$ and exit via $R'$. Finally, you can compute the shortest path in this directed graph.

The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$. For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A*. The vertices are the grid points labelled "0". You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked 0). You can solve this with either BFS or A*: BFS is simpler to implement, A* will run faster.

The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$. For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A*. The vertices are the grid points labelled "0". You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked 0). You can solve this with either BFS or A*: BFS is simpler to implement, A* will run faster.


If you additionally want to find the shortest path through all of the shapes (something that's not stated in the question), then you can fo the following: for all points $Q$ in shape $S_1$, and all points $R$ in shape $S_2$, calculate the shortest way to get from $Q$ to $R$ while avoiding shape $A$. Then add these as edges to a directed graph (where the length of the edge $Q\to R$ corresponds to the length of the shortest such path). Also add edges $R \to R'$ for each pair of points $R,R'$ in the same shape where you can enter the shape via $R$ and exit via $R'$. Finally, you can compute the shortest path in this directed graph.

Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$. For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A*. The vertices are the grid points labelled "0". You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked 0). You can solve this with either BFS or A*: BFS is simpler to implement, A* will run faster.