This question involves the problem of maze generation. That is$,$ generating a random network of

paths as a maze that fills an $nm$ grid, where $n$ corresponds to the number of rows and $m$ the

number of columns. In this problem, generated mazes must be fully connected and contain no

loops. Shown below is a $33$ grid and examples of valid mazes:

The following are examples of invalid mazes:

a$)$ Give an efficient algorithm to generate a random $nm$ maze. The algorithm must be

capable of generating all possible valid mazes, where a valid maze is fully connected,

contains no loops, and fills an $nm$ grid.

b$)$ Analyze the runtime of your algorithm.

c$)$ Give a strategy to select a valid entrance and exit.

do this with prims algorithm.