Each maze is represented as a string with the following format:

The maze consists of several lines of the same length, each terminated by the n (newline) character.

Excluding these newline characters, all characters are either # (hash/pound), or (space).

The hashtag character denotes a wall.

The space character denotes an empty location.

Exactly two locations on the boundary of the maze (first and last row and column) are spaces. All other locations are hashes. These two spaces are called exits.

For instance, the maze represented as the string

A maze solution is represented as a string identical to that of a maze, but with a path of o (lowercase letter O) symbols denoting a shortest path between the two exits of the maze. A shortest path consists of a minimum-length sequence of locations, each above, below, left, or right of the previous, beginning and ending with the locations of the exits. A solution to the maze above is:

NEED TO FILL OUT THE SOLVE.CPP BY IMPLEMENTING THE SOLVE.H, WE CAN INCLUDE A FUNCTION A VERTEX CLASS FUNCTION IN ORDER TO MAKE IT WORK.

MAIN.CPP

#include  #include  #include  #include "solve.h" using namespace std; inline void _test(const char* expression, const char* file, int line) { cerr  
 
 
 
 
SOLVE.H
 
 
 
 #ifndef SOLVE_H #define SOLVE_H #include  #include  #include  #include  #include  using namespace std; // For the mandatory running time, assume that the time for // operations of queue, unordered_set, and map are O(1). // (They are for average-case, but not worst-case). // // For the mandatory running time below, s is the length of // the input string representing the maze. // // For a complete description of the maze string // and maze solution formats, see the assignment pdf. // Returns a string representing a shortest solution to the maze. // Has undefined behavior if the maze is not valid or has no solution. // // Must run in O(s) time. string solve(string maze); #endif 
  which prints as:  which prints as