This C++ code is an example of a backtracking algorithm for exiting a maze. I ha

Question

This C++ code is an example of a backtracking algorithm for exiting a maze. I have to modify the code to print out the path without dead ends but it can include detours. So the basic idea is that the modified code will print out my processed maze and then print the pathway taken by the "mouse" without including any dead ends the mouse may have encountered. I have tried several different methods involing using stacks but I can't seem to find anything tha works.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

template<class T>
class Stack : public stack<T> {
public:
   T pop() {
       T tmp = top();
       stack<T>::pop();
       return tmp;
   }
};

class Cell {
public:
   Cell(int i = 0, int j = 0) {
       x = i; y = j;
   }
   bool operator== (const Cell& c) const {
       return x == c.x && y == c.y;
   }
private:
   int x, y;
   friend class Maze;
};

class Maze {
public:
   Maze();
   void exitMaze();
private:
   Cell currentCell, exitCell, entryCell;
   const char exitMarker, entryMarker, visited, passage, wall;
   Stack<Cell> mazeStack;
   char **store;
   void pushUnvisited(int,int);
   friend ostream& operator<< (ostream&, const Maze&);
   int rows, cols;
};

Maze::Maze() : exitMarker('e'), entryMarker('m'), visited('.'),
   passage('0'), wall('1') {
       Stack<char*> mazeRows;
       char str[80], *s;
       int col, row = 0;
       cout << "Enter a rectangular maze using the following "
           << "characters: m - entry e - exit 1 - wall 0 - passage "
           << "Enter one line at a time; end with Ctrl-z: ";
       while(cin >> str) {
           row++;
           cols = strlen(str);
           s = new char[cols+3];

           mazeRows.push(s);
           strcpy(s+1,str);
           s[0] = s[cols+1] = wall;
           s[cols+2] = '';
           if (strchr(s,exitMarker) != 0) {
               exitCell.x = row;
               exitCell.y = strchr(s,exitMarker) - s;
           }
           if (strchr(s,entryMarker) != 0) {
               entryCell.x = row;
               entryCell.y = strchr(s,entryMarker) - s;
           }
       }
       rows = row;
       store = new char*[rows+2];
       store[0] = new char[cols+3];
       for ( ; !mazeRows.empty(); row--) {
           store[row] = mazeRows.pop();
       }
       store[rows+1] = new char[cols+3];
       store[0][cols+2] = store[rows+1][cols+2] = '';
       for (col = 0; col <= cols+1; col++) {
           store[0][col] = wall;
           store[rows+1][col] = wall;
       }
}

void Maze::pushUnvisited(int row, int col) {
   if(store[row][col] == passage || store[row][col] == exitMarker) {
       mazeStack.push(Cell(row,col));
   }
}

void Maze::exitMaze() {
   int row, col;
   currentCell = entryCell;
   while(!(currentCell == exitCell)) {
       row = currentCell.x;
       col = currentCell.y;
       cout << *this;
       if (!(currentCell == entryCell))
           store[row][col] = visited;
       pushUnvisited(row+1,col);
       pushUnvisited(row, col+1);
       pushUnvisited(row-1,col);
       pushUnvisited(row,col-1);
       if (mazeStack.empty()) {
           cout << *this;
           cout << "Failure ";
           return;
       }
       else currentCell = mazeStack.pop();
   }
   cout << *this;
   cout << "Success ";
}

ostream& operator<< (ostream& out, const Maze& maze) {
   for (int row = 0; row <= maze.rows+1; row++)
       out << maze.store[row] << endl;
   out << endl;
   return out;
}
int main() {
   Maze().exitMaze();
   return 0;
}

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;

class Cell{
   public:
       int x;
       int y;
       int score;
       Cell(int a,int b,int sc){
           x     = a;
           y     = b;
           score = sc;
       }
}

class Path{
   public:
       Cell** maze;
       int row;
       int col;
       Path(int r,int c){
           row = r;
           col = c;
           maze = new Cell*[row];
           for (int i = 0; i < row; i++)
               maze[i] = new Cell[col];
       }
       void put(Cell* c){
           maze[c->x][c->y] = c;
       }
   int maximum_score_path(boolean[][] visit,int s_x,int s_y,int e_x,int e_y,int total){
       if (visit[s_x][s_y] == true || maze[s_x][s_y]->score == -1){
           return -1;
       }
       if ((s_x == e_x) && (s_y == e_y))
           return total;
       visit[s_x][s_y] = true;
       int max = -1;
       if (s_x - 1 >= 0){
           int temp = total + maze[s_x-1][s_y]->score;
           int res = maximum_score_path(visit,s_x-1,s_y,e_x,e_y,temp);
           if (res > max)
               max = res;
       }
       if (s_x + 1 < row){
           int temp = total + maze[s_x+1][s_y]->score;
           int res = maximum_score_path(visit,s_x+1,s_y,e_x,e_y,temp);
           if (res > max)
               max = res;  
       }
       if (s_y + 1 < col){
           int temp = total + maze[s_x][s_y+1]->score;
           int res = maximum_score_path(visit,s_x,s_y+1,e_x,e_y,temp);
           if (res > max)
               max = res;      
       }
       visit[s_x][s_y] = false;
       return max;
   }
}

int main(){
   int n,m;
   cin >> m >> n;
   Path* path = new Path(m,n);
   bool** v = new bool*[m];
   for (int i = 0; i < m; i++)
       v[i] = new bool[n];
   int score;
   for (int i = 0; i < m; i++){
       for (int j = 0; j < n; j++){
           cin >> score;
           Cell* cell = new Cell(i,j,score);
           path->put(cell);
       }
   }
   int result = path->maximum_score_path(v,m-1,0,0,n-1,path.maze[m-1][0].score);
      
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.