Build a MazeSolver.cpp

i have already had the interface of the mazesolver . Please help me implement it . C++

I am including all the information even the background information.

Thank you.

//MazeSolver.h #ifndef MAZE_SOLVER_H_

#define MAZE_SOLVER_H_

#include  #include  #include  #include #include

enum direction {SOUTH, EAST};

struct Position

{

 int row;

 int column;

};

class MazeSolver

{

public:

 //constructor

 //pre: input file is in correct format with first two values being integers

 // followed by valid maze characters in {'_', '*','$'}

 //post: if inuput file cannot be read outputs "Cannot read from input_file"

 // otherwise sets maze_rows_ and maze_columns_ from the first two values in input file

 // and allocates two 2-dimesional array of size maze_rows_ and maze_columns_

 // both maze_ and solution_ are initialized with characters read from input

 MazeSolver(std::string input_file);

 // destructor

 //post: deletes maze_ and solution_

 ~MazeSolver();

 //return: true if maze has been initialized, false otherwise

 bool mazeIsReady();

 //pre: maze_ has been initialized with valid character values in {'_', '*','$'}

 //post: solution_ has been marked with '>' signs along the path to the exit

 // prints "Found the exit!!!" if exit is found

 // or "This maze has no solution." if no exit could be found

 //return: true if exit is found, false otherwise

 bool solveMaze();

 //post: prints the solution to the standard output stream

 // with single space character between each maze character

 // and each maze row on a new line

 void printSolution();

private:

 //PRIVATE DATA MEMBERS:

 int maze_rows_ = 0; //the number of rows as read from input file

 int maze_columns_ = 0; //the number of columns as read from input file

 bool maze_ready = false; //indicates whether the maze has been initialized from input file

 char** maze_ = nullptr; //a 2-d character array containing maze characters read from input file

 char** solution_ = nullptr; //a 2-d character array containing maze characters copied from maze_

 // and path to exit marked with '>' characters and position backtracked from marked with '@'characters

 std::stack backtrack_stack_; //stack used for backtracking

 //PRIVATE MEMBER FUNCTIONS (helper functions)

 //pre: rows and columns are positive integers

 //post: allocates maze_ with rows and columns

 //called by constructor

 void initializeMaze(int rows, int columns);

 //pre: maze_ has been allocated with the correct number of rows and columns read from input file

 //post: fills in maze_ with characters read from input file

 //called by constructor

 void fillMaze(std::ifstream& input_stream);

 //pre: maze_ has been initialized with valid character values in {'_', '*','$'}

 // start position is always [0][0]

 //post: initializes solution_ with a copy of maze_

 // initializes backtrack_stack_ with all viable paths from position [0][0]

 // and mark the current position as visited ( '>' ) on solution_

 //called by constructor

 void initializeSolution();

 //pre: maze_ has been properly initialized

 //post: allocates solution_ to the correct number of rows and columns

 // and copies the contents of maze_ into solution_

 //called by initializeSolution()

 void copyMazetoSolution();

 //pre: current_position is a valid position on the maze_

 //post: adds all positions extensible from current_position to backtrack_stack_

 //return: true if path was extended, false otherwise

 //called by solveMaze()

 bool extendPath(Position current_position);

 //pre: old_position is a Position initialized with row and column to valid positions in maze_ and it is extensible in direction dir

 //return: a new Position on the maze moving in direction dir from old_position

 //called by extendPath()

 Position getNewPosition(Position old_position, direction dir);

 //checks if the path can be extended in maze_ from position current_position in direction dir

 //return: true if path can be extended given current_position and dir, false otherwise

 //called by extendPath

 bool isExtensible(Position current_position, direction dir);

}; // end MazeSolver

#endif /* MAZE_SOLVER_H_ */

Usage:

#include

#include "MazeSolver.h"

int main() {

MazeSolver solver("input.txt");

if(solver.mazeIsReady())

{

solver.solveMaze();

solver.printSolution();

}

return 0;

}

Input example: (Input.txt)

8 8 _ _ _ _ _ * _ * _ _ _ * _ _ _ _ _ * _ * _ * * * _ _ _ * * * _ _ * * _ _ _ _ * * * * _ * _ _ * * * * _ _ * * * * _ _ * _ _ _ _ $

Maze representation: In the input file the maze will be represented as a string of characters separated by spaces(') The first two characters in the input file will be integers representing the number of rows and columns. The remaining characters will be valid maze characters representing a maze If you think of a maze in terms of hallways and walls, the maze charactors are as follows: _ represents a hallway (input and output character) * represents a wall (input and output character) $ represents an exit (input and output character) > represents a PATH towards the exit (output character only) represents a location that has been visited and then BACKTRACKED out of on the solution (output character only) X represents a location that has been VISITED on the maze ("working" intermediary character on maze) Mazesolver w represent the maze and a solution as 2-dimensional arrays containing maze characters Simplifications: start position is always [O][0] and MazeSolver will search for a solution moving in two diroctions only (EAST and SOUTH)- unless it is backtracking Horo aro a samplo mazo and its solution maze Path solution Hallway Explored path after backtracking Wall k H Maze representation: In the input file the maze will be represented as a string of characters separated by spaces(') The first two characters in the input file will be integers representing the number of rows and columns. The remaining characters will be valid maze characters representing a maze If you think of a maze in terms of hallways and walls, the maze charactors are as follows: _ represents a hallway (input and output character) * represents a wall (input and output character) $ represents an exit (input and output character) > represents a PATH towards the exit (output character only) represents a location that has been visited and then BACKTRACKED out of on the solution (output character only) X represents a location that has been VISITED on the maze ("working" intermediary character on maze) Mazesolver w represent the maze and a solution as 2-dimensional arrays containing maze characters Simplifications: start position is always [O][0] and MazeSolver will search for a solution moving in two diroctions only (EAST and SOUTH)- unless it is backtracking Horo aro a samplo mazo and its solution maze Path solution Hallway Explored path after backtracking Wall k H