Computer Science

# Graphs: Level 5 Challenges

Do you like carrots?

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

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.

• Link and Ganondorf begin at different locations within the wood, Link as an 'L', and Ganondorf as a 'G'.
• Link gets to move first, taking a single step, or remaining still if he chooses. If he touches an uncollected Heart Piece, it becomes his, permanently.
• Ganondorf moves next, taking a single step, or remaining still if he chooses. If he touches an uncollected Heart Piece, it becomes his, permanently, and Link can never collect it.
• This process repeats until Link cannot collect any more Heart Pieces.
• Naturally, Ganondorf is a perfect logician, and will choose his steps optimally so as to minimize the number of Heart Pieces Link is able to collect.

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

• Link will always appear once per maze, as an 'L'.
• Ganondorf will always appear once per maze, as a 'G'.
• There will be at most five 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.
• Ganondorf plays optimally, with the explicit goal of minimizing the number of Heart Pieces Link collects. Both characters have perfect information at all times.
• Link and Ganondorf can freely pass through each other.
• $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 non-image content to Brilliant. Admin, feel free to delete this footnote if this is changed.

###### Image Credit: http://zelda.wikia.com/wiki/Ganondorf

How many pair of nodes $(u,v)$ in the following graph are there such that the shortest path between $u$ and $v$ is length $2$?

Details and Assumptions

×