# The Lost Woods - Evil Trees

Computer Science Level 5

The darkness of the woods continue, though nothing new or dangerous confronts the hero in these narrow, more compact realms of the wood. Full of magic and confident in his planning skills, Link now decides to tackle two challenges he's already faced at once: Collect all the Heart Pieces in the wood using as little magic as possible to remove Cuttable Trees. He quickly finds that, despite the apparent simplicity of the task, it's much harder than he first realized.

This link (1) contains a zip file, with a single file in the Input Format specified for this collection of problems, of $$1000$$ mazes.

Let $$S$$ be the sum of the score for each maze. We define the score to be the index of the maze (1-based) multiplied by the minimum number of Trees Link must cut if he wishes to obtain all of the Heart Pieces in the maze. There will be at least one Heart Piece, and at most three Heart Pieces in each maze, and all of them will be accessible. Note, however, that when Link cuts down a Tree, it stays cut down - he need not expend extra magic to pass through the same Tree in the same maze twice.

Find $$\boxed{S}$$ .

Example:

Input:

3
5 5
TT.TH
.#T#T
.T.#.
T#.#T
LT.T.
5 3
H.T.H
T###T
T.L.T
9 9
####H####
#.T...T.#
#T##T##T#
#.##.##.#
L.T.T.T.H
#.##.##.#
#T##T##T#
#.T...T.#
####H####


Output:

24


Output Explained:

In the first maze, there is only one Heart Piece, so we need only find the shortest path (in terms of number of trees) between Link and the Heart Piece. The best route is to go right, then all the way up, then right again, hitting only $$3$$ trees, so the score for the maze is $$1$$ (the index) times $$3$$.

In the second maze, Link can cut two trees to his left, and two trees to his right, to retrieve each of two Heart Pieces, but only one Tree separates the Heart Pieces them selves, so it is better to take that route after fetching the first Heart Piece. The score is thus $$2$$ times $$3$$.

In the third maze, each of three Heart Pieces, and Link, are separated by two trees in a clockwise fashion, so Link could go around the perimeter, cutting down $$6$$ trees, to collect all of them. However, in the center of the maze, there is a configuration of $$5$$ trees that separates everything. While it takes more magic to go from Link to any one Heart Piece through the middle than through the sides, it is more efficient to clear out the center trees, since he can then reach all of the Heart Pieces using only $$5$$ cuts, instead of $$6$$.

$$1 \times 3 + 2 \times 3 + 3 \times 5 = 24$$

Details:

• Link will always appear once per maze, as an 'L'.
• There will be at least one, and at most three Heart Pieces per maze, as 'H'.
• Open ground is given as '.'.
• Impenetrable trees are given as '#'.
• Cuttable trees are given as 'T'.
• No other characters will be present in each maze.
• Smaller mazes this time: $$1 \leq W,H \leq 10$$ in all mazes.

(1) - This link currently points to my Dropbox account, since there is currently no way to upload non-image content to Brilliant. Admin, feel free to delete this footnote if this is changed.