# The Lost Woods - Finding Hearts

**Computer Science**Level 5

Our hero, Link, finds himself in a forest most plain. Scattered around him, northways, eastways, westways and southways, are open plots of grass, impenetrable woods, and scattered, rare Heart Pieces. The question is: Can Link get all of them?

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 all indices (1-based) of mazes for which Link can access all Hearts within the maze, by moving up, down, left, or right through clearings and Heart Pieces, but not impenetrable forest. Find \(\boxed{S}\).

Example:

*Input:*

```
3
2 2
L#
#H
3 3
L..
##.
H..
6 6
H.....
.####H
.#.H#.
.#..#.
H####.
.....L
```

*Output:*

```
2
```

*Output Explained:*

In the first maze, there is one Heart Piece, but Link cannot access it - there are impenetrable trees in the way in both directions, and Link cannot move diagonally.

In the second maze, there is a single Heart Piece, and Link can access it by going right, right, down, down, left and left again, so we add its index, \(2\) , to the total.

In the third maze, there are four Heart Pieces, and while Link can reach three of them, the fourth is blocked off in the middle, so we do not add this maze's index to the total.

Thus, only \(2\) is added to the total, so the answer is \(\boxed{2}\) .

Details:

- Link will always appear once per maze, as an 'L'.
- There will be a positive number of Heart Pieces per maze, as 'H'.
- Open ground is given as '.'.
- Impenetrable trees are given as '#'.
- No other characters will be present in each maze.
\(1 \leq W,H \leq 150\) 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: http://www.piranhazone.com/index.php?language=1&page=zelda/mq&topic=ootmq005&pic=gc

**Your answer seems reasonable.**Find out if you're right!

**That seems reasonable.**Find out if you're right!

Already have an account? Log in here.