CPP CODE The case study at the end of Chapter 7 describes a

CPP CODE:

The case study at the end of Chapter 7 describes a recursive solution to determining whether or not a maze’s exit can be reached given some start cell. In this programming assignment you will adjust the implementation in a number of ways.The files are pasted below.

The files you should complete the implementation of are MazeDr.cpp, Maze.h, and Maze.cpp. An example test file is provided, maze1.

1. Describe the initial implementation. This can go in your details document

(at least two paragraphs).

2. Allow the maximum size of the input maze to be at least 50 × 50. Describe

in your details document what you had to change to achieve this.

3. Adjust the program to allow diagonal moves. Again, describe the changes

in your details document.

4. Return the path from the start cell to the exit by visually displaying the

nodes tested and where the nodes came from. You can do this by tracking

the parent cell of each node and displaying a different character than the

ones already defined. After returning whether or not a path exists the

maze with the path should be output.

5. Adjust the driver program to allow the user to specify whether or not a new

cell is being tested in the current maze or to load a new maze. This should

make testing easier for the user.

6. Create 5 different mazes with all of the sizes containing more cells than a

25 × 25 grid. Run your program on 5 different start/exit cells for each

maze. Remember your program should not only output whether or not a

path exists but also should visually display the path. Your input and output

should be submitted to receive full credit.

7. Discussion items to be included in your document: 1) Can you think of an

algorithm that would find a path to the exit better (it does not need to be

recursive)? Describe the algorithm. 2) What happens to environments with

multiple exits? 3) Does the algorithm that you coded return good paths? 4)

How would you change your program to only allow moves up and to the

right?

8. Submit a specification details document that describes the changes to the

program you made and implementation of your program.

//MazeDr.cpp

//Maze.cpp

//Maze.h

Solution

#ifndef vAlgorithms_Interview_graph_maze_better_h #define vAlgorithms_Interview_graph_maze_better_h static const int kMaxRows = 100; static const int kMaxColumns = 100; class MazeSolver { private: char m_matrix[kMaxRows][kMaxColumns]; //matrix representation of graph int rows, cols; //actual rows and columns bool m_exit_found; int m_exit_row, m_exit_col; int m_entrance_row, m_entrance_col; struct square //abstraction for data stored in every verex { pair m_coord; //x and y co-ordinates of the matrix square* m_parent; //to trace the path backwards square() : m_parent(0) {} }; queue Q; public: MazeSolver(const char* filename) : m_exit_found(false) , m_exit_row(0) , m_exit_col(0) , m_entrance_row(0) , m_entrance_col(0) { ifstream file; file.open(filename); if(!file) { cout << \"could not open the file\" << endl << flush; // in real world, put this in second phase constructor } init_matrix(file); } ~MazeSolver() { } void solve_maze() { //we will basically use BFS: keep pushing squares on q, visit all 4 neighbors and see //which way can we proceed depending on obstacle(wall) square* s = new square(); s->m_coord = make_pair(m_entrance_row, m_entrance_col); Q.push(s); while(!m_exit_found && !Q.empty()) { s = Q.front(); Q.pop(); int x = s->m_coord.first; int y = s->m_coord.second; //check if this square is an exit cell if(x == m_exit_row && y == m_exit_col) { m_matrix[x][y] = \'>\'; // end of the path m_exit_found = true; //todo: try breaking? no= queue wont empty } else { //try walking all 4 neighbors and select best path //NOTE: Since we check all 4 neighbors simultaneously, // the path will be the shortest path walk_path(x-1, y, s); walk_path(x+1, y, s); walk_path(x, y-1, s); walk_path(x, y+1, s); } } /* end while */ clear_maze(); //unset all previously marked visited shit //put the traversed path in maze for printing while(s->m_parent) { m_matrix[s->m_coord.first][s->m_coord.second] = \'-\'; s = s->m_parent; } /* end while */ } void print() { for(int i=0; i 0) { cols = line.size(); } } /* end while */ rows = row - 1; find_exit_and_entry(); m_exit_found = false; } //find and mark ramp and exit points void find_exit_and_entry() { for(int i=0; i\'; m_exit_found = true; } else { if(can_walk_at(x, y)) { //tag this cell as visited m_matrix[x][y] = \'-\'; cout << \"can walk = \" << x << \", \" << y << endl << flush; //add to queue square* s = new square(); s->m_parent = parent; s->m_coord = make_pair(x, y); Q.push(s); } } } bool can_walk_at(int x, int y) { bool oob = is_out_of_bounds(x, y); bool visited = m_matrix[x][y] == \'-\'; bool walled = m_matrix[x][y] == \'#\'; return ( !oob && !visited && !walled); } bool is_out_of_bounds(int x, int y) { if(x<0 || x > rows || y<0 || y>cols) return true; return false; } }; void run_test_graph_maze_better() { MazeSolver m(\"/Users/vshakya/Dropbox/private/graph/maze.txt\"); m.print(); m.solve_maze(); m.print(); } #endif