Create a new C++ source file named solve.cpp that implements the function declared in solve.h. Do not use any other library besides what is in solve.h and do not add any libraries to solve.cpp. It should only have #include "solve.h". Use a dynamic array and use breadth-first search.

 (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 

/////////////////////////////////////////////////////////////////////////////////////// (Main.cpp) #include  #include  #include  #include "solve.h" using namespace std; inline void _test(const char* expression, const char* file, int line) { cerr << "test(" << expression << ") failed in file " << file; cerr << ", line " << line << "." << endl; abort(); } #define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__)) int main() { // Setup string maze, soln; maze = ""; maze += "##### # "; maze += "# # "; maze += "# ##### "; soln = ""; soln += "#####o# "; soln += "#ooooo# "; soln += "#o##### "; test(solve(maze) == soln); maze = ""; maze += "##### # "; maze += "# # # "; maze += "# # # # "; maze += "# # # "; maze += "# ##### "; soln = ""; soln += "#####o# "; soln += "#ooo#o# "; soln += "#o#o#o# "; soln += "#o#ooo# "; soln += "#o##### "; test(solve(maze) == soln); maze = ""; maze += "######## "; maze += "# # "; maze += "# ## ### "; maze += "# # "; maze += "## ## ## "; maze += "# ## # "; maze += "## ### # "; maze += "## ### # "; soln = ""; soln += "######## "; soln += "# # "; soln += "# ## ### "; soln += "# oooo # "; soln += "##o##o## "; soln += "# o##oo# "; soln += "##o###o# "; soln += "##o###o# "; test(solve(maze) == soln); maze = ""; maze += "######## "; maze += "# # "; maze += "# ## ### "; maze += "# # "; maze += "# # # ## "; maze += "# ### # "; maze += "# ### # "; maze += "## ##### "; soln = ""; soln += "######## "; soln += "# #oooo "; soln += "# ##o### "; soln += "#oooo # "; soln += "#o# # ## "; soln += "#o### # "; soln += "#oo### # "; soln += "##o##### "; test(solve(maze) == soln); maze = ""; maze += "# ###### "; maze += "# # # "; maze += "# ## ### "; maze += "# # "; maze += "# # # ## "; maze += "# ### # "; maze += "# ### "; maze += "######## "; soln = ""; soln += "#o###### "; soln += "#o # # "; soln += "#o## ### "; soln += "#ooooo # "; soln += "# # #o## "; soln += "# ###oo# "; soln += "# ###oo "; soln += "######## "; test(solve(maze) == soln); maze = ""; maze += "######## "; maze += "# # "; maze += "# # "; maze += "# # "; maze += "## ## ## "; maze += "## ## # "; maze += "## ### # "; soln = ""; soln += "######## "; soln += "# # "; soln += "# # "; soln += "# oooo # "; soln += "##o##o## "; soln += "##o##oo# "; soln += "##o###o# "; test(solve(maze) == soln); maze = ""; maze += "######################################################### "; maze += "# # # # # # # # # # # "; maze += " ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## "; maze += "# # # # # # # # # # # "; maze += "######################################################### "; soln = ""; soln += "######################################################### "; soln += "#oooo #ooooooo # # #oooo # # #ooooooo #oooo #ooooooo# "; soln += "oo##o##o## ##o## ## ##o##o## ## ##o## ##o##o##o##o## ##oo "; soln += "# #oooo # #oooooooooo #oooooooooo # #oooo #oooo # # # "; soln += "######################################################### "; test(solve(maze) == soln); maze = ""; maze += "# ###################################### "; maze += "# ### ## ## # "; maze += "### ### ### # ###### ######## # # # # "; maze += "# # # # ## # # #### # ## "; maze += "# ####### # ##### # # ###### # # # "; maze += "# # # # # # # # ## # "; maze += "# ### ### ##### # # ######## # ##### # "; maze += "# ### # # ### # ## ### "; maze += "# # ### # ######## ####### # #### # "; maze += "# # # # ### # ## ## # ## # # "; maze += "# # # # ########## # #### # ## # # "; maze += "# # ##### # # ### # # # "; maze += "# # ## ####### # # # # ### #### "; maze += "# #### ## # # #### # ##### # # # # "; maze += "# ## ## ### ## # ## # # # ## "; maze += "## # # ###### ## ## ####### ## # # # ## "; maze += "# # # # ## # "; maze += "###################################### # "; soln = ""; soln += "#o###################################### "; soln += "#ooo###ooooo## ## # "; soln += "###o###o###o# ###### ######## # # # # "; soln += "# #ooooo# #o## # # #### # ## "; soln += "# ####### #o##### # # ###### # # # "; soln += "# #ooooo# # # # # # ## # "; soln += "# ### ### #####o# # ######## # ##### # "; soln += "# ### # #ooo### # ## ### "; soln += "# # ### #o######## ####### # #### # "; soln += "# # # # ### #oooooooooo## ## # ## # # "; soln += "# # # # ##########o# #### # ## # # "; soln += "# # ##### # #o### # # # "; soln += "# # ## ####### # #o# # ### #### "; soln += "# #### ## # # #### #o##### # # # # "; soln += "# ## ## ### ## #ooooooo## # # # ## "; soln += "## # # ###### ## ## #######o## # # # ## "; soln += "# # # # ## ooooooooooo# "; soln += "######################################o# "; test(solve(maze) == soln); cout << "Assignment complete." << endl; }