I am creating a maze using C++ and stacks but i need to create a solver. I have the psudeo code its like this:

Psudeo code

create an empty LocStack object

for ( row&col are 0; while neither row nor col are -1; pop new r and c from the stack)

if current location contains 'F' it is solved! so you return true

set the current location to 'o' to show it has been searched (the current location is amaze[row][col])

push all (possible) adjacent locations (row, col) onto stack:

if neighbor up (amaze[row-1][col]) is not outside or a wall or already done, push row-1, col

if neighbor right (amaze[row][col+1]) is not outside or a wall or already done, push row, col+1

if neighbor down (amaze[row+1][col]) is not outside or a wall or already done, push row+1, col

if neighbor left (amaze[row][col-1]) is not outside or a wall or already done, push row, col-1

Maze.h file

#ifndef MAZE_H #define MAZE_H

class Maze { private: char ** amaze; // The maze int rows; // Number of rows in the maze int cols; // Number of cols in the maze bool outside_or_wall_or_done(int row, int col); // Check if outside maze // or a wall or already searched public: Maze(); // constructor ~Maze(); // destructor void set_maze (char ** maz, int numr, int numc); bool solve_with_stack(); // solves maze, possible routes are stacked bool solve_with_queue(); // solves maze, possible routes are queued void print (); // prints current state of maze, // ' ' is open, 'X' is wall, 'F' is finish, 'o' is searched }; #endif /* MAZE_H */

LocStack.h file

#include #include #include #include

using namespace std;

class LocStack { // class private: struct StackNode { int row; // data Value int col; // data Value StackNode* next; // Ptr to next node };

StackNode* top; // top of stack

std::string hex(void* val); // converts pointer to hex string; used by print and others

public: // Constructor and Destructor LocStack() { top = nullptr; } ~LocStack(); // Destructor

// Stack operations void push(int r, int c); // Add a new node to the top of the stack. void pop(int& r, int& c); // Remove the top node and return its value. void peek(int& r, int& c); // Return the top node's value. void print(); // Output the contents of the stack to the screen };

#endif

LocStack.cpp

#include #include #include #include

#include "LocStack.h"

using namespace std;

LocStack::~LocStack() {

StackNode* sn = top;

// Traverse the entire list, deleting each node while (sn != nullptr) { StackNode* savedPtr = sn->next; cout << "Deleting Node: " << hex(sn) << " Row: " << sn->row << endl << " Col: " << sn->col << endl; //call destructor delete sn; sn = savedPtr; }

//set top to nullptr top = nullptr;

}

void LocStack::push(int r, int c) {

//set new sn pointer to the StackNode StackNode* sn = new StackNode; //set value and next sn->row = r; sn->col = c; sn->next = nullptr; //old top becomes second node sn->next = top; //new node becomes top top = sn; }

void LocStack::pop(int& r, int& c) {

//Cheking to see if the stack is empty if (top == nullptr) { c = -1; r = -1; cout << "The stack is empty." << endl; return; }

// not empty, remove first StackNode* second = top->next; r = top->row; // reference c = top->col; delete top; //set new top to the second top = second;

}

void LocStack::peek(int& r, int& c) { //cheking if the stack is empty if (top == nullptr) { // Error r = -1; // note reference c = -1; cout << "The stack is empty." << endl; return; } // not empty r = top->row; c = top->col; }

void LocStack::print() { //Printing value cout << " top: " << hex(top) << endl; //If the stack is empty if (top == nullptr) { cout << "The stack is empty. "; return; } //Not empty for (StackNode* sn = top; sn != nullptr; sn = sn->next) { //Printing value cout << "\t" << hex(sn) << ":" << "\tNext: " << hex(sn->next) << "\tRow: " << sn->row << endl << "\tCol:" << sn->col << endl; }

}

//Displaying in hex string LocStack::hex(void* val) { // Initialize the result string to begin with "0x". string hexStr = "0x";

// Compute how many hex digits in a pointer. // Two nibbles per byte, one hex digit per nibble. const unsigned PTR_DIGITS = sizeof(uintptr_t) * 2;

// Allocate a C-string to use as a buffer for the hex characters. char buf[PTR_DIGITS + 1]; // Add one for null char terminator

// Convert that pointer to hex digits (uppercase) snprintf(buf, sizeof(buf), "%0*zX", PTR_DIGITS, (uintptr_t)val);

// Concatenate the hex digits to 0x. hexStr = hexStr + buf;

// Return the resulting string. return hexStr;

} // end function hex

Maze.cpp file

#include

#include "Maze.h" #include "LocStack.h" //#include "LocQueue.h"

using namespace std;

// Constructor only initializes class variables. Maze::Maze() { rows = cols = 0; amaze = NULL; }

// Destructor doesn't have anything to do but is left as a place holder // for any future features that need cleanup. Maze::~Maze() { // Nothing to get rid of since we just point to the users supplied maze. }

// Attach a users maze. Keep track of number of rows and columns in it. void Maze::set_maze (char ** maz, int numr, int numc) { rows = numr; cols = numc; amaze = maz; }

// Determine if a row and column are outside the maze or // if they are inside the maze but a wall or already searched. // // Returns: // true for outside, wall or already searched. // false if its inside, open and unsearched. // bool Maze::outside_or_wall_or_done(int r, int c) { // Any row or column that is negative is outside. // Any row or column that is greater than the values passed to set_maze are outside. if (r < 0 || c < 0 || r >= rows || c >= cols ) { // Outside return true; } // ' ' is open, 'F' is the finish if (amaze[r][c] == ' ' || amaze[r][c] == 'F') { // not done, not wall return false; } // If we get here it is inside the maze but a wall or already done. return true; }

// YOUR COMMENTS GO HERE bool Maze::solve_with_stack () { // YOUR CODE GOES HERE

LocStack stack; for ( ){

This is where i need the code to go.

return false; }

// YOUR COMMENTS GO HERE bool Maze::solve_with_queue () { // YOUR CODE GOES HERE return false; }

// Print the current state of the maze. // Maze if made up of chars where: // ' ' is open, // 'X' is wall, // 'F' is finish, // 'o' is already searched // void Maze::print () { for (int row =0; row for (int col =0; col cout << amaze[row][col] << " "; } cout << endl; } cout << endl; }