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;
}
|