Implement a maze-solving C++ function. Both the input maze and output solution use an ASCII art map format (see Sections 4 and 5). Your code should solve large mazes in a fraction of a second.

The following files have been given to you:

1. A C++ header file (solve.h) declaring the solve function.

2. A C++ header file (vertex.h) declaring and implementing the Vertex class.

3. A C++ source file (main.cpp) containing a main function with tests.

Create a new C++ source file named solve.cpp that implements the function declared in solve.h, so that solve.cpp and the provided files compile into a program that runs with no failed tests. The code dor solve.h, vertex.h, and main.cpp are provided below.

////////////////////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.

// 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

////////////////////vertex.h////////////////////

#include

using namespace std;

// A helper class implementing a vertex in

// an adjacency-list-based graph.

class Vertex

{

public:

Vertex(int r, int c)

{

row = r;

col = c;

}

// Corresponding row and column location in maze

int row;

int col;

// List of neighboring vertices

vector neighs;

};

////////////////////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

srand(2018 + 'f');

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);

maze = "";

maze += "######################################################### ";

maze += " # # # # # # ";

maze += "# # # # # # # # # # # # # # ";

maze += "######################################################### ";

soln = "";

soln += "######################################################### ";

soln += "ooooo#oooooooo#ooooo#ooooo#oooooooooooooo#ooooo#ooooooooo ";

soln += "# #ooo# #ooo# #ooo# #ooo# #ooo# #ooo# # ";

soln += "######################################################### ";

test(solve(maze) == soln);

for (int t = 0; t < 100; ++t)

{

// Randomized test to prevent hardcoding

maze = "";

maze += "################################################## ";

maze += " ";

maze += "# # ";

maze += "################################################## ";

for (int i = 0; i < 4; ++i)

{

int offset = rand() % 5;

maze[58 + 10 * i + offset] = '#';

maze[108 + 10 * i + 3 + offset] = '#';

maze[108 + 10 * i - 1 + offset] = '#';

soln = maze;

int j = 51;

while (j < 101)

{

if (soln[j] == '#')

{

soln[j - 1 + 51] = 'o';

soln[j - 1 + 52] = 'o';

soln[j - 1 + 53] = 'o';

}

else

soln[j] = 'o';

++j;

}

}

test(solve(maze) == soln);

}

cout << "Assignment complete." << endl;

}