**Tags:** python ppc bfs

Rating:

# A_MAZE_ING (PPC) \[983\]

## __Solution__

Regular maze with doors "**{}**" and keys "**Om**". Target is "**<>**"

The problem is that we need the shortest path. Easy task for [BFS](https://en.wikipedia.org/wiki/Breadth-first_search)

The key idea here is find all possible routes through checkpoints (i.e. doors, keys, and the exit),

calculate their paths using BFS and choose the shortest.

That will guarantee that we will always get the shortest possible path

even on more complex mazes than we're given

1. Recursively search for all available checkpoints excluding those we already visited

and keeping track of the keys collected

2. Calculate the path for each route by concatenating paths produced by BFS

between 2 consecutive checkpoints. Every door except the door at the destination is ignored.

Remove first element from each path except the path between the first

and the second checkpoint because BFS returns both the starting and the final point.

3. Choose the shortest path

See source: [maze.py](https://github.com/MrRozdor/kksctf2019/blob/master/maze.py).

[`Vector`](https://github.com/MrRozdor/kksctf2019/blob/master/vector.py) is a simple 2d array-like vector which performs math operations

on x and y coordinates independently

Solve the maze many times and get the flag:

```

kks{A*_41g0ri7hm_|s_600D_3n0U6h!}

```

Original writeup (https://github.com/MrRozdor/kksctf2019/blob/master/A_MAZE_ING.md).