This is the MAze problem....
The first file goes like this ...
Code:
# include <list.h>
# include <vector.h>
# include <deque.h>
# include <iostream.h>
# include <fstream.h>
class cell
{
public:
// constructor
cell(int n) : number(n), visited(false) { }
// operations
void addNeighbor(cell * n) { neighbors.push_back(n); }
bool visit(deque<cell *> &);
protected:
int number;
bool visited;
list<cell *> neighbors;
};
class maze : backtrackFramework<cell *>
{
public:
maze(istream &);
void solveMaze();
protected:
cell * start;
bool finished;
deque <cell *> path;
};
maze::maze (istream & infile)
// initialize maze by reading from file
{
int numRows, numColumns;
int counter = 1;
cell * current = 0;
// read number of rows and columns
infile >> numRows >> numColumns;
// create vector for previous row
cell * nothing = 0;
vector<cell *> previousRow(numRows, nothing);
// now read data values
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numColumns; j++) {
current = new cell(counter++);
int walls;
infile >> walls;
// make north connections
if ((i > 0) && ((walls & 0x04) == 0)) {
current->addNeighbor (previousRow[j]);
previousRow[j]->addNeighbor (current);
}
// make west connections
if ((j > 0) && ((walls & 0x08) == 0)) {
current->addNeighbor (previousRow[j-1]);
previousRow[j-1]->addNeighbor (current);
}
previousRow[j] = current;
}
}
// most recently created cell is start of maze
start = current;
finished = false;
}
void maze::solveMaze ()
// solve the maze puzzle
{
start->visit(path);
while ((!finished) && (!path.empty())) {
cell * current = path.front();
path.pop_front();
finished = current->visit(path);
}
if (!finished) {
cout << "no solution found\n";
}
}
bool cell::visit (deque<cell *> & path)
// visit cell, place neighbors into queue
// return true if solution is found
{
if (visited) { // already been here
return false;
}
visited = true; // mark as visited
cout << "visiting cell " << number << endl;
if (number == 1) {
cout << "puzzle solved\n";
return true;
}
// put unvisited neighbors into deque
list <cell *>::iterator start, stop;
start = neighbors.begin();
stop = neighbors.end();
for (; start != stop; ++start) {
if (!(*start)->visited) {
// depth-first search
path.push_front(*start);
// breadth-first search
//path.push_back(*start);
}
}
return false;
}
void main ()
{
ifstream input("mazeone");
maze foo(input);
foo.solveMaze();
}