The Lost Woods - Cutting Trees

The forest is getting thicker, darker, and more dangerous. Heart Pieces are getting rarer, and open ground is no longer as abundant. Our hero now faces thick, but removable Trees in addition to the impenetrable ones, and while they are manageable, clearing Trees requires a fair bit of magic and work, so Link would prefer to cut as few Trees as possible.

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 in order to reach the singular Heart Piece in the maze. If Link can reach the Heart Piece without cutting any Trees, the score is zero for that maze. Link will always be able to reach the Heart Piece somehow, however.

Find \(\boxed{S}\).



3 3
5 5
10 1



Output Explained:

In the first maze, the Heart Piece is very close by if Link cuts the Tree, but if he takes the long way, he doesn't need to cut any, so the score is \(0\) .

Likewise, in the second maze, the Heart Piece is very close by if Link cuts the two Trees below, but if he takes the long way, he only needs to cut one Tree, so the score is \(2 \times 1\) .

In the third maze, Link has only one option, to cut the 8 trees in between him and the Heart Piece, so the score is \(3 \times 8\) .

\(0 + 2 \times 1 + 3 \times 8 = 26\)

Details and Assumptions:

  • Link will always appear once per maze, as an 'L'.
  • There will be exactly one Heart Piece, as 'H', and it will be accessible.
  • 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.
  • \(1 \leq W,H \leq 100\) 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.

This is a part of the collection entitled The Lost Woods, a series of problems in CS / Graph Theory.

Image Credit:

Problem Loading...

Note Loading...

Set Loading...