Reach the end by passing all required points
Given a grid of width W and height H containing 5 character types:
'S' means starting position
'E' means ending position
'C' means checkpoints
'.' means open position and player can pass through it
'#' means closed block that player cant pass through.
The goal of the player is to reach the end from the beginning at a minimum distance, but he needs to pass all the control points in the grid.
We need to find this minimum distance.
Some of the actions allowed by the player are as follows:
- The player can only move one step in a horizontal or vertical direction (up, down, left, right).
- Diagonal movement is NOT allowed.
- Distance is defined as the number of moves for different blocks.
- The player can pass open blocks, checkpoints, start and end points more than once as needed.
- If it is impossible to achieve the goal from the beginning, we need to say that it is impossible.
Example:
Let W=5
uH=5
# # # # #
# . C C #
# S # # #
# . . E #
# # # # #
Then the answer here is 9, since the path is:
(1,2) => (1,1) => (2,1) => (3,1) => (2,1) => (1,1) => (1,2) => ( 1,3-) => (2-3) => (3,3-)
Now W
they H
can reach 100 and the maximum number of control points can be no more than 18
One of the main approaches might be to use the entire shortest path of the pair here. But since there can be 10,000 nodes, complexity O(N^3)
with alogrims like Floyd-Warshall or Dijkstra will not serve the purpose.
What's their best approach for this question?
source to share
The cost of finding your way between checkpoints is the least of your concerns. For N
which is the number of checkpoints, this will grow to O(N*W*H)
, assuming you are just doing BFS from each checkpoint (and start and end nodes). However, if you have this easy part, you will still have to choose the order for the checkpoints. As other commenters have pointed out, this is a traveling salesman problem and you are not going to make it effective - this is inevitable O(N!)
. In comparison, if we discard the constant factors and use W=H=100, N=18
, the cost of the shortest paths is 180,000 "time units" ... and the cost of finding the best order for the control points is 6402373705728000 "time units". You may have noticed that this is a larger number.
source to share
Use a pathfinding algorithm like A * to find paths between two points, then you should decompose your problem like this: -
cost(S,E) = cost(S,C1)+cost(C2,C3)..cost(C3,C4)..cost(Ck,E)
There is a sequence of k!
breakpoints k
, so your algorithm will O(k!*N^2)
, and there can be no better algorithm, since this problem comes down to TSP .
source to share
I have faced the same problem in the past. I'll tell you how I did it.
I first used Dijkstra to determine the distances from S to C1 .... Ck
Then again for distances from C1 .... Ck then from C2 ... Ck, etc.
This will give you the shortest path from each control point to all the others, including the start and end.
Now create an adjacency matrix between each of the control points, including the origin and target.
In the end, use your traveling salesman to figure out the shortest route through the checkpoints.
If you don't know how to implement TSP, skip the last two steps, starting with the Adjacency matrix and use Bruteforce to determine the shortest path (takes more time, but ends up getting the job done).
I hope this helps
source to share