I can't complete the last test, it timeouts on move 17.
I am using A* to calculate paths, only considering known '.', 'T' and 'C' as valid pathways.
This is what I do:
- Look for the closest '?'
- Check if I have a valid path to it
- If so, keep moving towards it until it stops being a '?'.
- If not, look for the next-closest '?'
- Repeat that.
When I find the 'C' block, I keep checking if I have a valid path to it, and a path from it to 'T' that can be taken in the alarm time. If so, go to 'C' and go home.´
This works on all the others, spending a lot less than the 1200 fuel available, except on the last test. Kirk goes to (x, y) = (7, 11), which is a dead-end tunnel, with lots of '?' around that can't be accessed yet. The available '?' require going back from the tunnel and go the other way, which means they're quite far away. And so, the program gets a timeout while checking the closest '?'.
Does anyone have tips on this? I figure I either need to optimize the pathfinding function, so I can check more paths in the same time (which I'm not sure how to do), or implement some kind of logic to not check the path for a '?' if there's no path to a neighbouring '?', but I'm not quite getting it to work.
Edit: Just submited, and apparently the exact same thing happens on the 2 last validators