maze program rewrite, need help

ok i have a amazing.cpp which works, one must load a file from CMD prompt and have a txt file with a saved maze. the purpose of this program is to read in a maze and try to solve it.

ex
mazetest1.txt

has the following

111111
111001
1000e1
100m11
111111

my professor has reviewed my code and has made the point that i could remake this could using recursion only with no stacks and it would be shorter and better. he will only accept the code if i rebuild it using recursion, but i have no clue what to do or were to start, last day i can turn this project in is Wednesday the first. any help is greatly appreciated. i have worked hard and i do not want a zero on my assignment because my prof is being nit picky. this is my first time using templates and i a beginning programmer so i greatly appreciate any help

amazing.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <string>
#include <stack>
#include <cstring>
amazing.cpp
//created 7/10: last edit 7/30

using namespace std;

template<class T>
class Stack : public stack<T> {
public:
    T pop() {
        T tmp = stack<T>::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;//stack
    char **store;         // array of strings;
    void pushUnvisited(int,int);
    int rows, cols;
    friend 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;
    }
};

Maze::Maze() : exitMarker('e'), entryMarker('m'), visited('.'),
               passage('0'), wall('1') {
   Stack<char*> mazeRows;//stack
    char str[80], *s;
    int col, row = 0;
    cout << "Enter a rectangular maze using the following "
         << "characters:\nm - entry\ne - exit\n1 - wall\n0 - passage\n"
         << "Enter one line at at time; end with Ctrl-z:\n";
    while (cin >> str) {
        row++;
        cols = strlen(str);
        s = new char[cols+3];    // two more cells for borderline columns;
        mazeRows.push(s);
        strcpy(s+1,str);
        s[0] = s[cols+1] = wall; // fill the borderline cells with 1s;
        s[cols+2] = '\0';
        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];        // creates a 1D array of pointers;
    store[0] = new char[cols+3];      // a borderline row;
    for ( ; !mazeRows.empty(); row--) {
        store[row] = mazeRows.pop();
    }
    store[rows+1] = new char[cols+3]; // another borderline row;
    store[0][cols+2] = store[rows+1][cols+2] = '\0';
    for (col = 0; col <= cols+1; col++) {
        store[0][col] = wall;         // fill up the borderline rows with 1s;
        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;         // print a snapshot to screen
        if (!(currentCell == entryCell))
            store[row][col] = visited;
        pushUnvisited(row-1,col);
        pushUnvisited(row+1,col);
        pushUnvisited(row,col-1);
        pushUnvisited(row,col+1);
        if (mazeStack.empty()) {
             cout << *this;
             cout << "Failure\n";  // if maze fail return FAILURE
             return;
        }
        else currentCell = mazeStack.pop();
    }
    cout << *this;
    cout << "Success\n"; // maze is successful return SUCCESS
}

// driver
int main() {
    Maze().exitMaze();//start the maze
    return 0;
}
Last edited on
If you want to do this with recursion, consider the following:
A cell has four neighbors, each of which is in effect a 'mini-maze".
Let assume a function as follows:
 
bool Maze::Solve (CELL & cell);

Iterate through the maze to find the entry cell (or save it's position when 'm' is entered).
Call Solve for the entry cell.
..If the current cell is the exit cell, return true indicating you're done.
..If the current cell is a wall or out of bounds, return false indicating not done.
..If the cell is the entry cell or a passage, mark the cell as visited and call Solve() for each of that cell's four neighbors.
..If Solve() returns true (indicating the finished), exit current level of Solve() true (finished).
If the top level Solve() returns false, display "Failure".


Last edited on
Topic archived. No new replies allowed.