PLEASE assist Asap

Finding a path

Assume that we have not been given the steps that the robot took to go inside a maze and we are left with the task of getting the robot out of the maze. We can generalize this problem as finding a path from a start position to a goal position in a maze. A simple solution will simply have the robot navigate through available paths in the maze until it finds its way to the goal state, backtracking when it gets stuck. A backtracking algorithm for such a solution is the following:

Mark every square in the maze as unvisited.

Create an empty stack (of maze positions).

Push the start positions onto the stack, and mark the start square as visited.

If the stack is empty, you're done and the maze is unsolvable.

Let T be the top item on the stack. If T is equal to the finish square, you're done

and the stack contains a solution to the maze.

6. If all squares adjacent to T (i.e. the squares up, down, right, or left from T) are either blocked or are marked visited already, pop T off the stack and go to step 4.

7. Otherwise, select a square S that is adjacent to T, unvisited, and unblocked. Mark S as visited and push its positions on the stack. Go to step 4.

Warm-up Exercises

What would be the path found by the backtracking algorithm for the solving the following maze by choosing the adjacent squares in step 7, in the following order: Right, South, Left, North?

What would be the path found by the backtracking algorithm for the solving the following maze by choosing the adjacent squares in step 7, in the following order: Left, South, Right, North?

Use the below program (MAZEPATH.h), (MAZEPATH.CPP) to complete the following task

TASK 1. Write a client program (MazeClient.cpp) to create the following maze as an object of

the Maze class:

_________ |S......|

|...X...|

|...X...|

|.......|

|.......|

|.......|

|......G| ---------

TASK 2. Implement the solveBacktracking member function of the Maze class (Maze.cxx). Use the algorithm above.

TASK 3. Solve the maze created in TASK1 using the solveBacktracking function.

NOTE: You might need to add functions to the Maze class, depending on how you approach the solution. Add/modify the class as needed. But do not repeat functionality. Use the functions that are there when appropriate (e.g., the isClear function for checking if a cell is clear)

Consider a robot that has entered a warehouse to retrieve an item and must now find its way back to the entrance. Suppose the robot can move north, south, east, or west and that it has the following record of its moves:

To find its way out, the robot must reverse each step in the opposite order it took them. Write down the steps the robot must take to get out, given the steps above:

*Download the starter code for this part of the project. It contains a partial solution for the problem of a robot finding its way out of a warehouse. FILES: MazePath.cxx, MazePath.h, and MazePath.cpp

Complete the directionsOut() member function of the MazePath class and the overloaded output operator in the Path class.

Use the MazePathTest program to check whether your solution is correct.

Add a test to the MazePathTest program for the following steps:

NESWNESWNESWNESW (you have to figure out the solution and compare to it using assert; just look at the other tests in the MazePathTest program to understand how a test is written for a specific input value)

//MAZEPATH.h #include "MazePath.h" #include #include #include using namespace std; const string MazePath::DIRECTIONS = "NSEW"; const string MazePath::COMPLEMENTS = "SNWE"; MazePath::MazePath() { } MazePath::MazePath(string steps) { for (int ndx = 0; ndx < steps.size(); ndx++) { assert(DIRECTIONS.find(steps[ndx]) != string::npos); path.push(steps[ndx]); strPath.push_back(steps[ndx]); } } //takes a step further into the maze void MazePath::takeStep(char step) { if (DIRECTIONS.find(step) != string::npos) { path.push(step); strPath.push_back(step); } } //returns the sequence of steps to get back to the starting point string MazePath::directionsOut() { //your code here return ""; } //overloaded output operator ostream& operator<< (ostream &out, const MazePath &mazepath){ //your code here return out; } // overloaded assignmet operator MazePath& MazePath::operator= (const string &m) { MazePath mp(m); *this = mp; return *this; }

//MAZEPATHTESTPLEASE as.Cpp

#include "MazePath.h" #include #include using namespace std; int main () { //Testing isValid function with valid strings cout << " Running tests ... "; MazePath m("NEEESW"); assert(m.directionsOut() == "ENWWWS" && "NEEESW should give result ENWWWS"); m = "W"; assert(m.directionsOut() == "E"); m = "S"; assert(m.directionsOut() == "N"); m = "N"; assert(m.directionsOut() == "S"); m = "E"; assert(m.directionsOut() == "W"); m = "EEEEEEEE"; assert(m.directionsOut() == "WWWWWWWW"); m = "WWWWWWWW"; assert(m.directionsOut() == "EEEEEEEE"); cout << " Passed. "; }