# The Lost Woods - Lazy Hearts

**Computer Science**Level 4

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. This time, we wonder if Link can get just one of these Heart Pieces, and if so, how many steps he needs to take to reach it.

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 to reach a single Heart Piece, if he can. If no Heart Piece can be reached, the score for that maze is zero.

Find \(\boxed{S}\) .

Example:

*Input:*

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

*Output:*

```
50
```

*Output Explained:*

In the first maze, there is are two Heart Pieces, but the one on the left is closer, at \(2\) steps away instead of \(3\), so the score for the maze is \(1\) (the index) times \(2\).

In the second maze, there is a single Heart Piece, but it cannot be accessed, so the score for that maze is zero.

In the third maze, there is a single Heart Piece, and it is reachable in precisely \(16\) steps, so the score for this maze is \(48\).

\(2 + 48 = \boxed{50}\)

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 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: http://www.gamesradar.com/lost-woods-how-zeldas-enchanted-groves-inspired-forest-puzzling-mazes/

**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.