The Lost Woods - Cutting Trees

Plain old BFS and DFS are no longer sufficient to solve Link's problems. Now, we need to consider the concept of shortest path with unequal edge weights. There are many algorithms that do this, though some of them are a mite expensive for our graph sizes, such as A* , and Bellman Ford . In this solution, we'll go over an implementation of Dijkstra's Algorithm , which can be tuned to solve all mazes in this puzzle in $O(W \cdot H \cdot \log(W \cdot H))$ time.

An important note to consider going forward is that all Graphs which model the individual Lost Woods Mazes thus far are planar , have linearly as many edges as they do nodes, and as a result, have a constant, maximum vertex degree . These limits are not important now, but in future problems, they will make problems that are intractable on general graphs, tractable.

---

Dijkstra's Algorithm is an algorithm that, given a source node, can compute the minimum distance, or shortest path, to all other reachable nodes in the graph. The way it does this is fairly straight forward:

1) Assign a distance value to every node, with 0 at the source, and infinity at all other nodes, to start.

2) Make a list of tentative nodes, starting with all nodes adjacent to the source. Set the tentative distances of these nodes to be equal to the edge weights linking them to the source.

3) Choose the tentative node closest to the source (or select one arbitrarily if there's a tie), and mark its tentative distance as final.

4) Using that final distance, reach out to any adjacent nodes to add them to the list of tentative nodes, and adjust their tentative distances if necessary. (I.e., if final distance + edge weight to adjacent node < tentative distance of adjacent node, change the tentative distance to the new low).

5) Go to step 3, and repeat, until either a) the intended destination is reached, or b) there are no more tentative nodes.

The scale of the problem set, and the mazes within it, means that running Dijkstra with a naive, plain list for the tentative nodes will run in tractable time, at $O(W \cdot H \cdot (W + H))$ , due to the graph being planar. However, one can use a min-heap for the tentative node list instead, and this reduces the runtime per maze to $O(W \cdot H \cdot \log(W \cdot H))$ . It is even possible to get the runtime down to $O(W \cdot H)$ by taking advantage of the fact that all edge weights are in $\{0, 1\}$ .

---

To apply the algorithm to this problem, simply make the following transformations:

• Make all 'L', 'H', 'T', and '.' squares valid nodes in the graph.
• Make any edge that points to a 'T' have weight $1$ , and all other edges weight $0$ . This means that the weight of any shortest path will be equal to the number of Trees that had to be cut to take it, which is precisely what we're looking to minimize.
  • If backtracking were a possibility, this would not work, as we'd erroneously count cutting the same Tree twice. However, backtracking is not necessary in this problem, so this simplification is fine.
• Run Dijkstra's Algorithm with 'L' as the source, and 'H' as the destination.
• Return the distance to 'H' times the maze's index towards the sum.

---

Click this link to view the scores for each maze from the input in order, sans multiplication by the index. If you were not able to get the right answer, consulting these individual results may help you find the problem (or, if I got something wrong, the bug in my own solution!)