We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Without the travel restrictions on latitude and longitude, this is a standard dynamical programming problem, solved in O(n lg(n)) by processing the cities in order of increasing height and connecting each to the best-scoring city below (using a heap or BST for organising all cities already processed).
With the travel restrictions, I used a grid of BSTs with a grid resolution equal to dlat and dlong. Then only the BSTs at the cell containing the city being processed and the neighbouring cells have to be searched for the best lower neighbouring city. To avoid initialising a large grid of BSTs (most of which may never be used), I used a hash table keyed on the grid index.
Some other points: cities which even when connected to the bests route so far yield a negative score can be ignored, as can be routes with negative points.
Maximizing Mission Points
You are viewing a single comment's thread. Return to all comments →
Without the travel restrictions on latitude and longitude, this is a standard dynamical programming problem, solved in O(n lg(n)) by processing the cities in order of increasing height and connecting each to the best-scoring city below (using a heap or BST for organising all cities already processed). With the travel restrictions, I used a grid of BSTs with a grid resolution equal to dlat and dlong. Then only the BSTs at the cell containing the city being processed and the neighbouring cells have to be searched for the best lower neighbouring city. To avoid initialising a large grid of BSTs (most of which may never be used), I used a hash table keyed on the grid index. Some other points: cities which even when connected to the bests route so far yield a negative score can be ignored, as can be routes with negative points.