#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
 
struct node {
       node * prev;
       int x;
       int y;
       char marker;
};
 
class stack {
 
      public:
 
             stack ();
             void push (int, int, char);
             void pop ();
             int coordinates (int&, int&);
 
 
      private:
 
              node * top;
 
};
 
 
stack::stack () {
 
    top = NULL;
    top -> x = 0;
    top -> y = 5;    
 
}
 
 
void stack::push (int x, int y, char spotmarker) { // add a new node onto the stack
 
     if (top == NULL) {
 
             node * temp = new node;
             temp -> x = x;
             temp -> y = y;
	         temp -> marker = spotmarker;
	         temp -> prev = top;
	         top = temp;
    }
 
    else {
 
             node * temp = new node;
             temp -> x = x;
             temp -> y = y;
	         temp -> marker = spotmarker;
	         temp -> prev = NULL;
	         top = temp;
 
    }         
 
}
 
 
void stack::pop () { // remove the node off the stack
 
     node * temp = top;
     top = temp -> prev;
     delete temp;
 
}
 
int stack::coordinates(int &positionX, int &positionY) { // used to find current position
 
    positionX = top -> x;
    positionY = top -> y;
 
}
 
 
 
int main () {
 
    stack myStack; // creates instance of stack class
    char maze[10][10];
    int x, y;
    int xCurrent, yCurrent; 
    ifstream file; 
    ofstream output;
 
    file.open ("maze.txt");
 
    for (y = 0; y < 10; y++){
 
        for (x = 0; x < 10; x++){
 
            file >> maze[x][y];
            cout << maze[x][y];
 
        }
 
        cout << endl;
 
    }
 
    file.close ();
    cout << endl;
 
    myStack.push('*', 0, 5);
    while (xCurrent < 10 && yCurrent < 10){
 
        (x, y) = myStack.coordinates(x, y);  // IS THIS LEGAL?? IF NOT HOW DO YOU FIX IT?
 
        if(maze[x+1][y] == 'X' || maze[x+1][y] == ' '){
 
                x = x+1;
                maze[x][y] = '*';
                myStack.push('*', x, y);
 
        }
 
        else if(maze[x][y+1] == 'X' || maze[x][y+1] == ' '){
 
                y = y+1;
                maze[x][y] = '*';
                myStack.push('*', x, y);
 
        }
 
        else if(maze[x][y-1] == 'X' || maze[x][y-1] == ' '){
 
                y = y-1;
                maze[x][y] = '*';
                myStack.push('*', x, y);
 
        }
 
        else if(maze[x-1][y] == 'X' || maze[x-1][y] == ' '){
 
                x = x-1;
                maze[x][y] = '*';
                myStack.push('*', x, y);
 
        }
 
        else{
 
                myStack.pop();
 
        }
 
    xCurrent = x;
    yCurrent = y;
 
    }
 
    output.open ("pathtaken.dat");
 
    for (y = 0; y < 10; y++){
 
        for (x = 0; x < 10; x++){
 
            output << maze[x][y];
            cout << maze[x][y];
 
        }
 
        cout << endl;
 
    }
 
    output.close ();
 
    cin >> x; 
    return 0;
 
}

/***************************************************************************
 
The purpose of this program is to move through a given test maze.
You start at the starting point and work your way to the end of a 
10 X 10 maze.  The maze is read in through a data file.  The original
maze is printed onto the screen and then is worked through.  There is
also a data file that will give you the path taken with *'s representing
where you have travelled inside the maze.  This file will essentially
be the same maze as you read in with the exception of the *'s replacing
the X's.  The final path will also be printed out to the screen.
 
 
File "testmaze.dat" needed to read in the maze.
Output can be found in the file "pathtaken.dat".
 
 
Stack class and header file are written into this file and not 
seperate files for the simple sake of making submission easier.
 
***************************************************************************/
 
 
// defining the needed libraries
 
#include <iostream> // used for cin/cout
#include <cstdlib> // used for NULL
#include <fstream> // used for file input and output
using namespace std;
 
struct node {  
       node * prev; 
            // prev is used instead of next for
            // readability due to the fact that
            // you have to backtrack through the maze
       int x;
       int y;
       char marker;
};
 
class stack {
 
      public: 
             // functions that are needed for this stack
             // push will add new information to the top of the stack
             // pop will take off the information
             // coordinates will return where you are located
             stack ();
             void push (int, int, char);
             void pop ();
             void coordinates (int&, int&);
 
 
      private:
              // top works where we would normally have next
              // however we define it as top since we are using 
              // a stack and stacks only interact with the top element
              node * top;
 
};
 
 
// functions for the stack class
 
 
stack::stack () { // constructor used to initialize values
 
    top = NULL;
    top = new node;
    top -> x = 0;
    top -> y = 5;    
 
}
 
 
void stack::push (int x, int y, char spotmarker) { 
     // adds a new node onto the stack
     // int x and int y are used to keep track of your position
     // spotmarker is used to replace X's you have travelled on
     // with *'s to note your final path
 
     if (top == NULL) {
 
             node * temp = new node;
             temp -> x = x;
             temp -> y = y;
	         temp -> marker = spotmarker;
	         temp -> prev = NULL;
	         top = temp;
    }
 
    else {
 
             node * temp = new node;
             temp -> x = x;
             temp -> y = y;
	         temp -> marker = spotmarker;
	         temp -> prev = top;
	         top = temp;
 
    }         
 
}
 
 
void stack::pop () { 
     // remove the node off the stack
     // this is used for backtracking 
 
     node * temp = top;
     top = temp -> prev;
     delete temp;
 
}
 
void stack::coordinates(int &positionX, int &positionY) { 
    // used to find current position
    // int positionX and int positionY are call by reference variables
    // they return the position you are currently occupying
 
    positionX = top -> x;
    positionY = top -> y;
 
}
 
 
// main program
 
 
int main () {
 
    stack myStack; // creates instance of stack class
    char maze[10][10]; // two dimensional array for maze given in data file
    int x = 0, y = 0; 
    int xCurrent = 0;
    ifstream file; // creates instance of input file
    ofstream output; // creates instance of output file
 
    file.open ("testmaze.dat"); //reads in data file for starting maze
    cout << endl << endl;
    cout << "This is the maze you are trying to solve." << endl << endl;
    for (y = 0; y < 10; y++){ // makes the columns for the y coordinates
 
        for (x = 0; x < 10; x++){ // makes rows of the x coordinates
 
            file >> maze[x][y];  // reads the maze from the input file
            cout << maze[x][y]; //prints maze to screen
 
        }
 
        cout << endl;
 
    }
 
    file.close (); // closes input file testmaze.dat
    cout << endl;
    cout << "This is the path taken to solve the maze." << endl << endl;
    output.open ("pathtaken.dat"); //stores path information in this data file
    myStack.push('*', x, y);
 
    while (xCurrent < 10){ 
 
          // you are out of the array and maze 
          // boundries if you reach 10
          // the array is 10 X 10 starting at 0 and 
          // ending with element 9
 
        myStack.coordinates(x, y);  //retrieves coordinates
         cout << x << " " << y; // added to see what values were
        if(maze[x+1][y] == 'X'){ // go right
 
                x = x+1;
                maze[x][y] = '*';
                myStack.push('*', x, y);
 
        }
 
        else if(maze[x][y+1] == 'X'){ // go up
 
                y = y+1;
                maze[x][y] = '*';
                myStack.push('*', x, y);
 
        }
 
        else if(maze[x][y-1] == 'X'){ // go down
 
                y = y-1;
                maze[x][y] = '*';
                myStack.push('*', x, y);
 
        }
 
        else if(maze[x-1][y] == 'X'){ // go left
 
                x = x-1;
                maze[x][y] = '*';
                myStack.push('*', x, y);
 
        }
 
        else{
            cout << "bob" << endl; // added as a marker to see
                                   // if it was skipping if statements
                myStack.pop(); // backtracks through the maze if needed
 
        }
 
        xCurrent = x;
 
    }
 
 
    for (y = 0; y < 10; y++){ // makes the columns for the y coordinates
 
        for (x = 0; x < 10; x++){ // makes rows of the x coordinates
 
            output << maze[x][y]; // stores the maze into the output file
            cout << maze[x][y]; // prints path taken to screen
 
        }
 
        cout << endl;
 
    }
 
    output.close ();  // closes the output file pathtaken.dat
 
    cin >> x; 
    return 0;
 
}