Computer Science
# Graph Algorithms

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

Last time, Sally moved through her garden eating an apple in every square.

But this time Sally feels more enthusiastic. This time she's going to do the same but now, she can also move diagonally. Find the number of ways in which Sally can eat all 25 apples

**Details and Assumptions**

She has a $5 \times 5$ garden with total of 25 apples.

She can move forward, backward, up, down or diagonally as long as there is an apple in the cell she is moving to.

She is standing in the center of the garden, i.e. $3^{\text{rd}}$ row and $3^{\text{rd}}$ column.

If the garden was of size $3 \times 3$, then she can eat all the apples in exactly 32 ways.

**Warning**

- The best C++ code (so far) takes nearly 100 seconds on a
**Quad Core**$2.67$**GHz**processor. So, it's okay if your code is running for long.

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.