Solution to planning bunnies escape? about google-foobar-help HOT 1 CLOSED

Just had a quick look over the Java.

I think the first step you would want to calculate the shortest distance from start to finish using Dijkstra for example to give you an upper bound.vNow you know that there could be a better possible solution, depending on how you represent data you could store the shortest path to each point from start so you know how long it takes to get from start to every node.

Because you know the current upper bound; go to each wall and calculate distance from wall to end without crossing any other walls again. You will get an answer wallToEndDistance which you will need to add to startToWallDistance. Compare totalDistance to currentMin. You only need to calculate the algorithm for the starting node, and every wall that startToWallDistance < currentMin. After you exhausted all possible walls you have the min, I think you were calculating DFS too many times as it was recursive but really distance calculations should only be called 1-30 times.

There is actually a way to do this using A* if you prefer to use that, the data structure used by A* may be more helpful.

It might be worth storing the nodes aa a data structure that contains x y isWall and distance, distance = startToNode, then also having a list of wall nodes. This way you can just refer to your list and see which wall you have not calculated all the shortest distance for. For weight you can just use isWall*100000 + 1 for example.

from google-foobar-help.