Author : Zahorodnyi Oleksandr

For the completion of Task #2 Maze, I used the Growing Tree algorithm. I chose this algorithm because it allows for generating high-quality mazes while also supporting flexible configuration — it can behave more like Prim’s algorithm or like a standard DFS. This is achieved through the parameter p — the probability with which we either take the last node from the list (DFS) or a random one (Prim’s). In the program, this value is chosen randomly within a given range, so each new maze has different settings, and the program is designed in such a way that these settings can be easily adjusted. In general, the program is implemented so that it can be easily extended and improved.

The algorithm has a time complexity of O(N × M) and a space complexity of O(N × M), where N and M are the dimensions of the maze matrix.

Usage maze generator:

First compile the generator, then run it like this:

./maze_generator (width) (height) [traps]

(width), (height) : integers >= 7, dimensions of the matrix

[traps] : optional integer in [0..5], count of traps in maze

Usage tester:

First compile checker, then run tester like this:

./tester.sh <num_tests>

num_tests - number of random tests

Output :

# - wall

. - passage

E - entrance

X - exit

T - trap

$ - treasure