$3)$ Write solveMazeBFS$()$

Now you're ready to tackle a function that searches the maze for a solution path:

Vector solveMazeBFS$($Grid& maze$)$

Solving a maze can be seen as a specific instance of a path$-$finding problem, where the challenge is to find a route from the entrance to the exit. Path$-$finding comes up in a variety of situations such as packet routing on the internet, robot motion planning, analyzing gene mutations, spell correction, and more.

Breadth$-$first search $($BFS$)$ is a classic and elegant algorithm for finding a path. A breadth$-$first search considers paths outward from the entry location in a radial fashion until it finds the exit. The first paths examined take one hop from the entry. If any of these reach the exit location, success! If not, the search expands to those paths that are two hops long. At each subsequent step, the search expands radially, examining all paths of length three, then of length four, and so on$,$ stopping at the first path that reaches the exit.

Breadth$-$first search is typically implemented using a queue. The queue stores partial paths that represent possibilities to explore. The first paths enqueued are all length one, followed by enqueuing the length two paths, and so on$.$ Because a queue processing elements in FIFO order, all shorter paths are dequeued and processed before the longer paths make their way to the front of queue. This means paths are tried in order of increasing length and thus a solution path found via breadth$-$first search will be the shortest possible such solution.

At each step, the algorithm considers the current path at the front of the queue. If the current path ends at the exit, it must be a completed solution path. If not, the algorithm considers the current path, extends it to reach locations that are one hop further away in the maze, and enqueues those extended paths to be examined in later rounds.

Here are the steps followed by a breadth$-$first search:

Create an empty queue of paths. Each path is a Vector and the queue of paths is of type Queue$>.$

A nested ADT type like this looks a little scary at first, but it is just the right tool for this job!

Create a length$-$one path containing just the entry location. Enqueue that path.

In our mazes, the entry is always the location in the upper$-$left corner, and the exit is the lower$-$right.

While there are still more paths to explore:

Dequeue the current path from queue.If the current path ends at exit:

You're done. The current path is the solution!

Otherwise:

Determine the viable neighbors from the end location of the current path. A viable neighbor is a valid move that has not yet been visited during the searchFor each viable neighbor, make copy of current path, extend by adding