Part One:
Captain, Interrupted
Thanks to your ingenious plan, you escape the reliquary alive and with a trove of useful information about Eos. One thing is now clear: before anything else, you must find your friends.
Among the documents you recovered from the reliquary is a curious magical scroll bearing a large map and an incantation. According to its notes, the map reveals the location of anyone you name, as long as they exist somewhere in your current timeline. It's a long shot, since you have neither heard from Captain Xarlos directly, nor have you heard rumors of any other travelers like yourself, but you decide its worth trying.
You take a breath, hold the scroll flat, and speak the words aloud:
"Karuk Shi Na Hael! Captain Xarlos!"
The parchment trembles. A glowing stain of luminescent blood-red spreads across its surface, and two bright points flare into view. One marks you. The other lies far, far away yet undeniably present. This must be where Caprain Xarlos is! He is in the same timeline as you. A wave of relief passes through you, tempered with worry. You just hope he hasn't been eaten by a wild cat, a dinosaur, or whatever else this place has lurking around…
Determined to reach him, you examine the map more closely. Your marker, your current position, sits in the top-left corner of the map (index 0, 0). Captain Xarlos' distant marker is surrounded by twisting terrain and impassable barriers, each indicated by a blocky # symbol. Every open space costs one unit of distance to traverse, and barriers cannot be crossed. Movement is only possible to adjacent squares to the North, South, East, and West, and never diagonal. To reach him as quickly as possible, you'll need to compute the shortest possible route, step by step, from your position to his.
The scroll, your puzzle input, contains:
- The position on the map of Captain Xarlos' location on the first line, with row and column separated by a space.
- A terrain map consisting of spaces and # on the remaining lines, representing traversable and blocked squares of the map.
For example:
With this example puzzle input:
7 8 ################ ###### #### ##### ####### ########## ## # ######## ## ###### # ## # # ##### ######## ###### ### ###### #### ### #### ###################You get a map like this withyour location (・) at 0,0 andthe captain (@) at 7,8.
| ・ | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # |
| # | # | # | # | # | # | # | ||||||||||
| # | # | # | # | # | # | # | # | # | # | # | # | |||||
| # | # | # | # | # | # | |||||||||||
| # | # | # | # | # | # | # | # | # | # | # | ||||||
| # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | ||
| # | # | # | # | |||||||||||||
| # | # | # | # | # | # | @ | # | # | # | # | # | # | # | |||
| # | # | # | # | # | # | # | # | # | ||||||||
| # | # | # | # | # | # | # | # | # | # | # | # | # | ||||
| # | # | # | # | # | # | # | ||||||||||
| # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # |
The shortest path from yourlocation to Captain Xarlos follows this red line.
| ・ | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # |
| # | # | # | # | # | # | # | ||||||||||
| # | # | # | # | # | # | # | # | # | # | # | # | |||||
| # | # | # | # | # | # | |||||||||||
| # | # | # | # | # | # | # | # | # | # | # | ||||||
| # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | ||
| # | # | # | # | |||||||||||||
| # | # | # | # | # | # | @ | # | # | # | # | # | # | # | |||
| # | # | # | # | # | # | # | # | # | ||||||||
| # | # | # | # | # | # | # | # | # | # | # | # | # | ||||
| # | # | # | # | # | # | # | ||||||||||
| # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # | # |
The shortest path is 35 units long.