//
//	test of maze routine
//
//	Described in Chapter 11 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//

# 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 {
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 neighbors into deque
	list <cell *>::iterator start, stop;
	start = neighbors.begin ();
	stop = neighbors.end ();
	for ( ; start != stop; ++start)
		if (! (*start)->visited)
			path.push_front (*start);
	return false;
}


void main () {
	ifstream input ("mazeone");
	maze foo(input);
	foo.solveMaze();
	}