When I first read the problem I said to myself - well, that shouldn't be too hard: just use D*(Lite) to navigate to the goal in unknown terrain and then back to start. But a few moments later I realized that just using D* is not enough here, at the minimum because there is no information about the goal node (thank you problem authors )
So the only realistic algorithms that came to my mind were these:
Full map discovery (based on the comment from Elliot)
1. Discover the map by using recursion or greedy mapping where you always move to the closest unknown cell. You need to make sure not to step into the control room before discovering the whole map as you may not manage to come to start before the alarm goes off (this can be done by temporarily marking the control room as a wall)
2. When the map is open, use any short-path algorithm to move to the control room and then the same algorithm to move to start
- Only need 2 simple algorithms in sequential use
- No complex logic or conditionals
- You need more fuel and the chance to run out of it is much larger (though this doesn't seem to be the case with the current test cases)
Partial map discovery
- As before, discover the map using recursion or greedy mapping. This time you need to stop when the target cell becomes visible (there may be a wall between your current position and the target cell)
- Use D* to navigate from the current location to the target cell considering unknown cells as free. Stop immediately before reaching the target cell - you don't want to get there unless you know there is a safe way back.
- Considering all unknown cells as walls, use D* (or other algorithm) to calculate the path from target to start. If the path is short enough then you're done - just walk into the control room and then navigate back to start
- If the path is too long (which could happen if the undeterministic algorithm at step 1 didn't take you on the shortest path to the target) then use step 1 to discover the next unknown cell
- Repeat 3-5
- Uses less fuel. In most cases the solution can be found without fully discovering the map
- Complex logic
- Usage of the more advanced D*(Lite) algorithm
Regardless of the algorithm, this problem may not always be solved because there are inputs for which the solution cannot be found by any algorithm or it can be found only by chance. Take this example (where the corner with C is not yet known):
. . #C
. ## .
. ## .
T . . .
If you're given up to 11 fuel units or up to 5 moves to reach the start node after the alarm was triggered then there is no solution, no matter the algorithm.
If you're given fuel for only 12-13 moves, this can only be achieved if you were lucky enough to start exploring the map by moving to the right (obviously by changing the map you may not be as lucky next time)