MazeReaper==========(Script available [here](https://github.com/antihorsey/ctf-writeups/blob/master/3dsctf-2017/MazeReaper/maze.py))
Upon connecting to the server given in the problem statement, you are presentedwith the following:
```
                    +++     3DSCTF - MAZEREAPER     +++
 [+] After being captured by the Grim Reaper, you were taken to a secret reaping     room for the secret games of death.
                                      ...                                    ;::::;                                  ;::::; :;                                ;:::::'   :;                               ;:::::;     ;.                              ,:::::'       ;           OOO                              ::::::;       ;          OOOOO                              ;:::::;       ;         OOOOOOOO                             ,;::::::;     ;'         / OOOOOOO                           ;:::::::::`. ,,,;.        /  / DOOOOOO                         .';:::::::::::::::::;,     /  /     DOOOO                        ,::::::;::::::;;;;::::;,   /  /        DOOO                       ;`::::::`'::::::;;;::::: ,#/  /          DOOO                       :`:::::::`;::::::;;::: ;::#  /            DOOO                       ::`:::::::`;:::::::: ;::::# /              DOO                       `:`:::::::`;:::::: ;::::::#/               DOO                        :::`:::::::`;; ;:::::::::##                DO                        ::::`:::::::`;::::::::;:::#                DO                        `:::::`::::::::::::;'`:;::#                D                         `:::::`::::::::;' /  / `:#                          ::::::`:::::;'  /  /   `#
 [+] As The Death loves to play with its victims, it loosed you at the     beginning of a maze with a map and said: "There are keys and doors     scattered around the labyrinth.The distance between each connected room is     unitary. number of hits possible, I will not take your soul and I will set     you free. "
 [+] Since she released you, you have highlighted the following     information on the map:     - A line with four values: number of rooms (nr), number of corridors       between rooms (NC), number of keys (NK), number of doors (ND).     - A line with the position that The Death left you (SP) and the place of       the exit (EP).     - A list of NC corridors between two rooms.     - A list of NK with key locations (lower case).     - And a list ND with the doors (capital letters) that need keys.
 [+] Example:                                          +-+                                          | |                          +---------------+-++-+--------+           +--+| |        |           |SP|        +----------------+--++-+        |           +--+        |                |EP|           +-+---------+  +------+-+                +--+           |a|                   |A|                |           +-+                   +-+                |                                   |                |                                   +------+-+-------+                                          | |                                          +-+
 [+] For the example the answer is 4.
 [+] Sometimes The Reaper plays with no escape mazes. If this occurs,     answer with -1.
 [+] Type 'start' for try to runaway:```
I was taken aback by the instructions at first, so let me clarify: In the imageabove, in the lower right corner those are lines connecting A and EP, that'snot a giant room. The specification of that scenario would look something like:
`7 7 1 1` : 7 rooms, 7 corridors, 1 key, 1 door
`3 7` : start in room #3, exit in room #7
```1 22 33 43 54 64 76 7```
Corridors connecting the rooms
`2 a` : key 'a' in room #2
`4 A` : door 'A' requiring key 'a' in room #4
The shortest route would then be start in room 3 and move to room 2 to pick upkey 'a', move back to room 3, move to room 4 and unlock A, move to room 7 andexit. A total of 4 moves.
That being said, the way to solve is pretty straightforward, at least forproblems that aren't much larger than this. Just run a standard breadth-firstsearch, except instead of storing just your position for the state, also storewhich keys you currently have. If you've already visited a room but had adifferent set of keys, then you've hit a new state and should keep that in yoursearch queue. If you've already visited a room and have the same set of keys,then you've already hit this state. Since it's a breadth-first search, you knowthe previous path to get there was shorter, so discard the new duplicate state.
That makes for an upper bound of R * 2<sup>K</sup> possible states, where R isthe number of rooms and K is the number of keys. The final level of thischallenge was R=200 and K=20, for an upper bound of 209,715,200 states.Probably couldn't have done much bigger mazes than this, but this will sufficefor the challenge.
This algorithm would probably have been a lot faster if I represented the keysand doors as bitvectors and did bitwise operations to test for access insteadof manipulating strings all over the place, but this got the job done.
Solve 50 challenges and you'll receive the following message:
``` [+] Nice, the flag is: 3DS{br4vElY_Fac3_th3_$oUL_r3Ap3R}```