// find a path in a maze

#include <iostream.h>
#include <fstream.h>
#include "stack.h"

const numMoves = 4;

class Maze;
class Position {
	friend Maze;
	int row, col;
public:
	friend bool operator==(const Position& l, const Position& r);
	friend bool operator!=(const Position& l, const Position& r);
	friend istream& operator>>(istream& in, Position& M);
	friend ostream& operator<<(ostream& out, const Position& M);

};

bool operator==(const Position& l, const Position& r)
{
	return (l.row == r.row)&&(l.col == r.col);
}

bool operator!=(const Position& l, const Position& r)
{
	return (l.row != r.row)||(l.col != r.col);
}

class Maze
{
	int maze[12][12], m, n;
	Stack<Position> *path; 
	friend istream& operator>>(istream& in, Maze& M);
	void initOffset (Position p[]);
public:
	bool FindPath(Position orig, Position dest);
	void OutputPath(ostream& );

};

istream& operator>>(istream& in, Position& M)
{
	return in >> M.row >> M.col;
}

ostream& operator<<(ostream& out, const Position& M)
{
	return out << "(" << M.row << ", " << M.col << ")";
}

istream& operator>>(istream& in, Maze& M)
{
   in >> M.m >> M.n;
   for (int i=1; i<=M.m; i++)
      for (int j=1; j<=M.n; j++) in >> M.maze[i][j];
   
   // initialize wall of obstacles around maze
 
	  for (i = 0; i <= M.n+1; i++)
		M.maze[0][i] = M.maze[M.m+1][i] = 1; 
	  for (i = 0; i <= M.m+1; i++)
		M.maze[i][0] = M.maze[i][M.n+1] = 1; 
   return in;
}

void Maze::initOffset(Position offset[])
{
   offset[0].row = 0; offset[0].col = 1; // right
   offset[1].row = 1; offset[1].col = 0; // down
   offset[2].row = 0; offset[2].col = -1; // left
   offset[3].row = -1; offset[3].col = 0; // up
}

bool Maze::FindPath(Position orig, Position dest)
{
   Position offset[numMoves];
   initOffset(offset);
   path = new Stack<Position>(m*m);

   int option = 0;
   Position here=orig;
   maze[here.row][here.col] = 1; 

   while (here != dest)
   {
      int r, c;      
      while (option < numMoves)
	  {
         r = here.row + offset[option].row;
         c = here.col + offset[option].col;
         if (maze[r][c] == 0) break;
         option++; 
      }

      if (option < numMoves)// move to maze[r][c]
	  {
		path->Add(here);
        here.row = r; here.col = c;
        maze[r][c] = 1;
        option = 0;
      }
      else // no neighbor to move to, back up
	  {
         if (path->IsEmpty()) return false;
         Position next;
         path->Delete(next);
         if (next.row == here.row) // figure out next move
            option = 2 + next.col - here.col;
         else option = 3 + next.row - here.row;
         here = next;
       }
   }
   return true;  
}

void Maze::OutputPath(ostream& out)
{
   out << "The path is" << endl;
   Position here;
   while (!path->IsEmpty())
   {
      path->Delete(here);
      out << here << endl;
   }
}

void main(void)
{
   Maze M;
   ifstream infile("maze.dat");
   ofstream outfile("maze.out");
   infile >> M;
   Position orig, dest;
   cout << "Please input the origin: ";
   cin >> orig;
   cout << "Please input the destination: ";
   cin >> dest;

   if (M.FindPath(orig,dest))
	   M.OutputPath(outfile);
   else
	   outfile << "No path" << endl;
}