Santa's Shortest Path Problem
Trying to be as time-efficient as possible Santa needs to plan his trips carefully. Given a 5X5 grid representing a map of villages it is your task to be Santa's flight controller. Show santa the shortest and therefor fastest route to fly his sleigh and give him a list of coördinates (or directions) to follow. Be carefull though, do not let Santa crash, nor get him arrested!
- In the examples '□' represents a village on the map Santa has to visit;
- In the examples '■' represents a no-fly zone or obstacle (antenna, mountain etc.) Santa can't cross;
- Input is any representation of a 'grid' with villages and obstacles;
- POI's can be any given character to help you make a distinction between villages and obstacles (1's and 0's for example);
- Santa can only fly horizontally and vertically on this grid;
- Santa has to start at
A1on the grid. His starting position is excluded from the result;
- Santa can go back the way he came, meaning: he can visit the same coördinates multiple times;
- Return Santa an array (or concatenated string) of coördinates ranging from A1-E5 which represents a route that visits all villages in the shortest manner possible;
- Coördinates ranging from A1-E5 are prefered, but smart Santa could read any list of clues that could lead him as long as it takes him step-by-step through the grid, e.g:
- In case of a tie, present Santa with a single option;
- One can assume all villages are reachable;
- This is code-golf, so shortest code wins!
I did come across some related posts:
But the tasks seem to be quite different.