#include <iostream>
#include <fstream>
#include <iomanip>
#include <time.h>
using namespace std;

int REC_calls=0, CUR_depth=0, MAX_depth=0;

template<typename T>
class Node
{
public:
    Node(T t):data(t), next(NULL){};
    T getdata() {return data;};
    Node<T> *next;       // The client program (list) needs to maintain the link, so public.
private:
    T data;              // We don't want the data to be changed directly. 
};


template<typename T>
class Stack
{
public:
    Stack();
    Stack(Stack<T> & st); // Important!!
    void push(T data); 
    T pop();
    bool isempty();
    ~Stack();  // Delete every node in the list.
    friend Node<T> *peek_top(Stack<T> & s);  // This is not a good idea. 
private:
    Node<T> *top;
};

template<typename T>
Stack<T>::Stack()     // Can't go like Stack::Stack()
:top(NULL) {}

template<typename T>               // Copy constructor
Stack<T>::Stack(Stack<T> & st)     // Need & st
{
    if (st.top == NULL) 
    {
        top=NULL;
        return;
    }
    Node<T> *cur, *next, *new_node;
    cur = new Node<T>((st.top)->getdata());
    next=cur->next=(st.top)->next;
    top = cur;
    while (next != NULL)
    {
        new_node = new Node<T>(next->getdata());
        next=new_node->next=next->next;
        cur->next=new_node;
        cur=new_node;
    }
}


template<typename T>
void Stack<T>::push(T data)   
{
    Node<T> *new_node; 
    new_node = new Node<T>(data);
    new_node->next = top;
    top = new_node;
}

template<typename T>
T Stack<T>::pop()   
{
    T data;
    if (top==NULL) return data;
    Node<T> *node=top;
    data=top->getdata();
    top = top->next;
    delete node;
    return data;
}


template<typename T>
bool Stack<T>::isempty()   
{
    return (top==NULL);
}

template<typename T>
Stack<T>::~Stack()     // Destructor
{
    while (top!=NULL) pop();
}

template<typename T>
Node<T> *peek_top(Stack<T> & s)   
{
    return s.top;
}



class Position
{
public:
    Position():x(0), y(0) {};
    Position(int a, int b) :x(a), y(b) {};
    bool operator ==(Position p) { return(p.x == x && p.y == y); };
    void moveE() {x++;};
    void moveW() {x--;};
    void moveN() {y--;};
    void moveS() {y++;};
    friend class Maze;
private:
    int x;
    int y;
};

class Maze
{
public:
    int maxx;
    int maxy;
    char maze[80][40];
    bool valid_move(Position m)
        { return( m.x >=0 && m.y >=0 && 
                  m.x < maxx && m.y < maxy &&
                  maze[m.x][m.y]=='+');};
    void mark(Position m) {maze[m.x][m.y]='*';};
    void mark(Position m, char x) {maze[m.x][m.y]=x;};
    void unmark(Position m) {maze[m.x][m.y]='x';};

};

void print_maze(Maze m)
{
    int i,j;

    cout << "Maze: " << m.maxx << " X " << m.maxy << endl;
    for (i=0; i<m.maxy; i++)
    {       
        for (j=0;j<m.maxx;j++)
        {
            cout << setw(1);
            switch (m.maze[j][i])
            {
            case '.': cout << char(127); //'X'; 
                break;
            case '+': cout << " ";
                break;
            default: cout << m.maze[j][i];
            }
        }
        cout << endl;
    }
    cout << "Recursive calls: " << REC_calls;
    cout << ",   Max depth: " << MAX_depth << endl;
}

// This is a non-recursive version
bool gothrough(Maze & m, Position start, Position dest, 
               Stack<Position> & returnpath)
{
    Position temp(start), curpos(start);

    while (!(curpos == dest))
    {
        m.mark(curpos);
        returnpath.push(curpos);
        MAX_depth = (MAX_depth > ++CUR_depth ? MAX_depth : CUR_depth);
        temp.moveE();   //////////////////// Try East
        if (m.valid_move(temp)) 
        {
            curpos = temp; continue;
        }
        temp=curpos;
        temp.moveS();   //////////////////// Try South
        if (m.valid_move(temp)) 
        {
            curpos = temp; continue;
        }
        temp=curpos;
        temp.moveW();   //////////////////// Try West
        if (m.valid_move(temp)) 
        {
            curpos = temp; continue;
        }
        temp=curpos;
        temp.moveN();   //////////////////// Try North
        if (m.valid_move(temp)) 
        {
            curpos = temp; continue;
        }
        // All 4 if's fail; No way through this curpos;
        m.mark(curpos,':');         // Mark it so won't try it again.
        returnpath.pop();           // Remove this pos from stack.
        if (returnpath.isempty())   // Or, you can go-- if(CUR_depth == 0).
            return false;           // There is no return, a dead maze.
        curpos = returnpath.pop();  // Return to previous pos.
        CUR_depth -= 2;             // 2 in stack are gone. 
    }
    m.mark(curpos);
    returnpath.push(curpos);
    return true;
}

// This is a recursive version
bool gothrough(Maze & m, Position p1, Position p2)
{
    MAX_depth = (MAX_depth > ++CUR_depth ? MAX_depth : CUR_depth);
    REC_calls++;
    if (p1 == p2) 
    {
        m.mark(p1);
        CUR_depth--; return true;
    }
    Maze nextm(m);
    Position temp=p1;

    nextm.mark(p1);

    temp.moveE();   //////////////////// Try East
    if (nextm.valid_move(temp) && gothrough(nextm,temp,p2))
    {
        m=nextm; CUR_depth--; return true;
    }

    nextm=m;
    nextm.mark(p1);
    temp=p1;
    temp.moveS();   //////////////////// Try South
    if (nextm.valid_move(temp) && gothrough(nextm,temp,p2))
    {
        m=nextm; CUR_depth--; return true;
    }

    nextm=m;
    nextm.mark(p1);
    temp=p1;
    temp.moveW();   //////////////////// Try West
    if (nextm.valid_move(temp) && gothrough(nextm,temp,p2))
    {
        m=nextm; CUR_depth--; return true;
    }

    nextm=m;
    nextm.mark(p1);
    temp=p1;
    temp.moveN();   //////////////////// Try North
    if (nextm.valid_move(temp) && gothrough(nextm,temp,p2))
    {
        m=nextm; CUR_depth--; return true;
    }
    CUR_depth--; return false;
}


int main()
{
    Maze m;
    int i,j;
    char dummy, mazefile[80];
    long timemark;
    bool thereisaway;
    
while (true)
{
    cout << "\nInput a maze file:";
    cin >> mazefile;
    cin.ignore(100,'\n');

    ifstream mazefilestream(mazefile);
    if (mazefilestream.fail()) 
    {
        cout << "Can't open the file -- " << mazefile << endl;
        return 0;
    }
    mazefilestream >> m.maxx >> m.maxy;
    mazefilestream.ignore(100,'\n'); // The first three lines of the 
    mazefilestream.ignore(100,'\n'); // file are useless to us; 
    mazefilestream.ignore(100,'\n');
    for (i=0; i<m.maxy; i++)
    {       
        for (j=0;j<m.maxx;j++)
              mazefilestream.get(m.maze[j][i]);  // [y][x]
        mazefilestream.ignore(100,'\n');
    }
    mazefilestream.close();
    Position start(0,0), dest(m.maxx-1, m.maxy-1); // Starting position and
                                                   // destination. 
    Maze dupm(m);  // Duplicate the maze, so we can restore.
    REC_calls = MAX_depth = CUR_depth = 0; // For recording the stack or 
                                           // Recursion depth.
    print_maze(m); // print the original maze.
    Stack<Position> path;

    cout << "\nPress return to solve this maze.";
    cin.get(dummy);

    timemark = clock();
    thereisaway = gothrough(m, start, dest, path); // Non-rec version callled 
    cout << "\nSolved in " << clock() - timemark << " ms!!\n";

    if (thereisaway)
    {
        cout << "\nPress return to see the result.";
        cin.get(dummy);
        print_maze(m);      // This maze now contains wrong trials info.
        m = dupm;
        Position p;
        while (!path.isempty()) {
            p = path.pop();
            m.mark(p);
        }
        cout << "\nPress return to see the result without wrong trails.";
        cin.get(dummy);
        cout << "\nWrong trials removed:\n";
        print_maze(m);
    }
    else
        cout << "\nNo Way!!\n";

    cout << "\nPress return to run a recursive version.";
    cin.get(dummy);

    m = dupm;   // restor the maze. 
    REC_calls = MAX_depth = CUR_depth = 0; // For recording the stack or 
                                           // Recursion depth.
    timemark = clock();
    thereisaway = gothrough(m, start, dest);
    cout << "\nSolved in " << clock() - timemark << " ms!!\n";
    if (thereisaway)
    {
        cout << "\nPress return to see the result.";
        cin.get(dummy);
        print_maze(m);
    }
    else
        cout << "\nNo Way!!\n";
}
    return 0;
}