The Lost Woods - Travelling Swordsman

Computer Science Level 5

Heart Pieces are abundant for our hero now, and nothing stands in his way to get them, for this time, our hero knows that each and every Heart Piece within the wood is accessible to him. However, all of this collecting has brought a want for efficiency into Link's mind. How can the hero move to collect every Heart Piece available using as few steps 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 steps Link must take in order to collect every available Heart Piece in the maze. It is guaranteed that all of the Heart Pieces are accessible to Link.

Find \(\boxed{S}\).



6 1
3 3
7 7



Output Explained:

In the first maze, Link could either go left and then right, or right and then left. In the former case, it would take \(7\) steps to collect both pieces, and in the latter, it would take \(8\) steps, so the score for the first maze is \(1 \times 7\) .

In the second maze, Link can go directly to any corner, then simply walk the perimeter of the wood to collect every Heart Piece. There is no one best route in this case, but that does not matter, for they all require the same number of steps: \(8\) .

In the third maze, once again, Link needs to choose which Heart Piece to go for before heading directly for the other one. Heading for the one in the middle turns out to be faster, and this yields a total of \(40\) steps.

\(1 \times 7 + 2 \times 8 + 3 \times 40 = 143\)

Details and Assumptions:

  • Link will always appear once per maze, as an 'L'.
  • There will always be at least 2, and at most 10 Heart Pieces. All of them will be accessible.
  • Open ground is given as '.'.
  • Impenetrable trees are given as '#'.
  • 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:
Image Credit:
Sources combined by me.

Problem Loading...

Note Loading...

Set Loading...