Already have an account? Log in here.
Whether you're finding the shortest path between two locations or modeling a social network, graphs are are a critical tool for storing data and exploring connections.
Given this \(100 \times 38\) maze with two exits, find out the number of steps (left, right, up and down), including the step out of the maze, from the worst point inside, i.e, the point from which it takes the longest to get out.
The maze is presented in an obvious format. Absence of 
or 
represent absence of walls. Walls on the boundaries which are absent are exits.
To clarify, the title image is a joke. It has got nothing to do with the maze the problem links to.
Example
The worst point of the following \(3 \times 5\) maze is the lower left corner. It takes 9 steps to get out from that point
1 2 3 4 5 6 7 

Already have an account? Log in here.
The king of the desert, and Link's arch nemesis, Ganondorf, has learned of the hero's rampant collecting of Heart Pieces, and that hardly aligns with his evil designs. Determined to stop the hero from progressing, the evil king has entered the Lost Woods himself, to collect Heart Pieces before Link can get them.
This link (1) contains a zip file, with a single file in the Input Format specified for this collection of problems, of 100 mazes.
Let \(S\) be the sum of the score for each maze. We define the score to be the index of the maze (1based) multiplied by the maximum number of Heart Pieces Link can collect despite Ganondorf's interference.
Find \(\boxed{S}\) .
Example:
Input:
4
5 5
##.##
..G..
H###H
.###.
..L..
5 5
##L##
.....
H###H
.###.
..G..
5 5
##.##
..G..
H#.#H
.#.#.
..L..
7 4
##L.G##
H.#.#.H
#.....#
H.###.H
Output:
13
Output Explained:
In the first maze, Ganondorf can indefinitely mimic Link's movements left and right until he becomes adjacent to a Heart Piece, which he can then collect before Link can, and then go fetch the second one before Link as well. Though Link can prolong the opening indefinitely, he will never collect a single Heart Piece either way, so the score for this maze is \(0\).
In the second maze, Link and Ganondorf are in opposite positions as the first maze, with Link set back one space to compensate for firstturn advantage. Despite this, Link cannot employ the same strategy Ganondorf did  if he did, Ganondorf could simply sit still indefinitely, and Link would never collect a Heart Piece, which is Ganondorf's optimal end result. Link must therefore sacrifice one Heart Piece to Ganondorf by going after the other one, making the score for this maze \(1\) times the index.
In the third maze, the situation is similar to the first maze, but now Link has a new avenue of approach. Though the path down the middle is longer towards each Heart Piece than the paths down the sides, by going up the middle Link forces Ganondorf to choose a single Heart Piece to defend, sacrificing the other to Link, making the score for this maze \(1\) times the index.
In the fourth maze, Link is equidistant from all four Heart Pieces, same as Ganondorf, so with first turn advantage, he can get at least one. However, no matter which path Ganondorf takes, Link will also be able to get a second Heart Piece, but not a third, if he reacts properly to Ganondorf's movements. The score for this maze is thus \(2\) times the index.
\(1 \times 0 + 2 \times 1 + 3 \times 1 + 4 \times 2 = 13\)
Details:
\(1 \leq W \times H \leq 30\) in all mazes.
(1)  This link currently points to my Dropbox account, since there is currently no way to upload nonimage content to Brilliant. Admin, feel free to delete this footnote if this is changed.
Already have an account? Log in here.
Details and Assumptions
The length of a path is the number of edges it has.
The graph is given in an adjacency matrix representation.
Already have an account? Log in here.
Problem Loading...
Note Loading...
Set Loading...