Tags: ppc java bfs

Rating:

Okay, we have interactive task with mazes. We need to solve all mazes (about 20-40) in ~5 mins ( (c)Author).

It is a classical task to find a way in maze, but have some additionals: We have keys(Om) and Gates(or doors, {}), and we need to solve task with minimum turns.

**Step 1:**
Let's solve task without keys and doors.

We have 2 good algos: [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) and [DFS](https://en.wikipedia.org/wiki/Depth-first_search). It is easy to understand, that second algo will helps us to find answer, but without minimum path. Then we will use first algo.

Little trick: in BFS we didn't need to go to previous cell. Then we will use some array to keep in memory about this.
BFS guarantee us, that we will have minimum path.

**Step 2:**

Let's mark our map(array) with next states:
0 - cell is free
1 - cell is not free (#)
2 - cell contains key(Om)
3 - cell is a gate

Next, we need to use some weights-map array. This massive will have a memory about last state of turn in this. (We need to save how much length of path here and how much keys user have at this moment).

And now, some algo to solve, can we go in this cell:
If current cell in map is 3 (gate) and we didn't have keys
So we will skip this turn.
If current cell not initialized ( == null) AND current cell(in memory) have keys >= current keys AND current cell(in memory) have turns <= current turns
So we will skip this turn.
If current cell in map is 2 (key)
Set in map current cell as 0 ( we can do this, because we know, that BFS search only shortest path to cell), update weights-map, and update keys that we have (increment by 1)
If current cell in map is 3 and we have keys
Update weights-map, and update keys that we have (decrement by 1)
If current cell in map is 0
Update weights-map

About data that we need to keep:
1) x
2) y
3) path (like "urrrddu")
4) keys

Then the problem is solved as usual on the BFS algorithm.

Here you can find my solution: [Github](https://github.com/HerrLeStrate/open.kksctf-2019/blob/master/amazeing.java)

Original writeup (https://github.com/HerrLeStrate/open.kksctf-2019/blob/master/amazeing.java).