The Lost Woods - Foreword

Introduction:

Cue music.

Welcome to The Lost Woods! The fabled forest is a home to many mysteries, myths, and legends, with no small number of challenges to be taken within its far reaching boundaries. Whether you are a beginner, an amateur, an expert, or even if you've never tackled such challenges before, there is certainly something for you here.

These problems are based almost entirely in the realm of Graph Theory. Some of them may simply be classical applications of well known graph problems, requiring very little adaptation on the programmer's part to go from a standard algorithm to one that solves the given problem. Others require more advanced thinking, deeper knowledge of Graph Theory, stronger programming implementation skills, or perhaps some combination of all three.

While the problems themselves will be self-contained, and you will not need to be familiar with advanced CS and Graph terminology to understand the problem, solving the problems often will require such knowledge. At the very least, you should have medium strength or more in some programming language you can execute with, as these problems are not intended to be hand-solvable. It's also recommended that if you intend to tackle multiple problems in this set, to write your code out in a reusable way - some problems may be direct expansions of previous problems, or they may be more easily solved using methods explored in older, more unrelated problems.

Format:

This format is common to all problems in the set. If you followed a link that said 'Input Format' to this note, this is what you're looking for!

While every problem will be unique in terms of what must be solved for, and how the output must be formatted, the input format for each problem will be the same, excepting special markers, so it is highly recommended you make your input-parsing code as reusable as possible. The formal specification is thus:

• The first line in the file will contain a single number, $T$. This will be the number of grids for which you must solve the given puzzle. $T \geq 1$ always.
• This will be followed by $T$ mazes, each of the following format:
  • The first line will have two numbers separated by a space: $W$ and $H$. These indicate the width and height of the grid, respectively, and $W, H \geq 1$ always.
  • The next $H$ lines will each contain $W$ characters, representing the state of the grid.

Characters:

• $\text{\#}$ represents dense, impenetrable forest. Nothing can pass through it.
• $\text{.}$ represents open ground, through which everything can pass.
• $\text{L}$ represents Link's starting location, if applicable to the current problem. The square is considered to be open ground for traversal purposes.
• $\text{H}$ represents a Heart Piece, something Link often tries to collect. The square is considered to be open ground for traversal purposes.
• Other characters may be defined in the problem statement to represent other things.

Example:

3
3 2
L#H
.#.
5 5
H..#H
##.#.
..L..
.#.##
H#..H
1 7
#
#
#
L
#
#
#

Ranking:

These problems are arranged, subjectively by me, in what I perceive to be an increasing level of difficulty. Since I learned graph theory and programming paradigms in a particular order, and it is very likely that order is not the same order you learned things in, it is very likely you will not perceive the difficulty order of the problems to be perfectly increasing, and perfect consensus will therefore very likely be unattainable. That said, if there's some problem that seems woefully out of order, raise an objection and if there's enough yay-sayers I'll be happy to move it.

Introductory Problems:

These are basic, introductory problems. If you have a degree in CS you should be fine skipping these, but taking them on as a warmup might be preferable.

• Finding Hearts

• Lazy Hearts

Intermediate Problems:

These problems require more intermediate difficulty Graph Theory algorithms and concept knowledge. If you have a degree in CS, you may have forgotten some of these if it's been a few years.

• Cutting Trees

• Travelling Swordsman

Advanced Problems:

These problems are designed to be challenging to all participants. If the Introductory Problems aren't a walk in the park for you, these problems are quite possibly too advanced for your current skill set. Tread cautiously.

• Enter Ganondorf

• Evil Trees

NO SPOILERS:

• Please don't post problem solutions or attempts on any of the notes for this set. If you have clarification questions, or wish to discuss solutions, use the appropriate channels for the individual problems as if they were stand-alone.
• All other discussion is perfectly welcome on the notes.