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

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

The answer is 452582.

1 solution

Daniel Ploch
Jan 14, 2016

There are multiple ways to solve this problem, all equally valid. The idea at the core is Graph Traversal , where BFS and DFS are perhaps the two most commonly known ways of traversing a graph.

The condition for each index is "Link must be able to access all the Heart Pieces." One simple way of answering this question is first to ask "How many Heart Pieces are there?", followed by "How many Heart Pieces can Link reach?", finished by "Are these two numbers the same?" Equivalently, one could ask the more advanced question, "Are all of the Heart Pieces in the same connected component as Link?" We'll detail the solution to the first set of questions.

First, we scan the maze in. Count the H's, and remember where L is.
Second, we run a BFS from the L position, and count the number of H's we come across. Pseudo-code:

visited = set[link]
node_list = [link]
reachable_hearts = 0
while node_list is not empty:
  new_node_list = []
  for node in node_list:
    for adj_node in node.adjacent_nodes():
      if adj_node.value is not '#' and adj_node not in visited:
        visited.add(adj_node)
        new_node_list.add(adj_node)
        if adj_node.value is 'H':
          reachable_hearts++
  node_list = new_node_list

Third, if reachable_hearts is the same as the total counted earlier, add the index of that maze to the total.

Click this link to view the scores for each maze from the input in order ( $1$ if all hearts are reachable, $0$ if not). If you were not able to get the right answer, consulting these individual results may help you find the problem (or, if I got something wrong, the bug in my own solution!)

The Lost Woods - Finding Hearts

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

The answer is 452582.

1 solution

0 pending reports