/*	File:	maze.cpp





			Christer Karlsson



			    

Implements a code to find shortest path

through a maze



The program first reads in the file describing

the maze. Hash the maze description into a vector

of integer vectors.  It fully explores the whole

access level before going to the next level.

The path is reported including the total cost

that includes the step-in and step-out cost. 	*/





#include <iostream>

#include <fstream>

#include <string>

#include <vector>

#include <queue>

#include <stack>



using namespace std;



const int MAZE_SIZE = 101;



/**********************  ERROR FUNCTION  ********************************/

void error (char* s, const char* s2 = "") {

  cerr << s << " " << s2 << "\n";

  exit(1);

}



void error (char* s, int s2) {

  cerr << s << " " << s2 << "\n";

  exit(1);

}

/**********************END ERROR FUNCTION********************************/



/*********************  PRINT ROUT FUNCTION  ****************************/    

void PrintRout(stack<int> rout)

{

    int cost = 1;

    cout << "Start";

	while ( !rout.empty() )

	{

		cout << " -> " << rout.top() << endl;

		cout << rout.top();

		rout.pop();

		cost++;

	}

    cout << " -> Exit\n\n" << "Total cost: " << cost << endl << endl;		

}

/******************END ROUT QUEUES FUNCTION****************************/

/********************   HASH FUNCTION   *******************************/

/*The Hash function, to hash the maze file*/

void Hash(vector< vector <int> > &hashtable, const char* fname)

{

    char word[5];

    int hash;

    

    /* Read in the Maze */

	cout << "Reading in the Maze File\n";

	cout << "this might take a second\n\n";    



    ifstream Path(fname);

    int l=0;    

    while (Path >> word)

    {

        if (l==0)

            hash = atoi(word);

        else   

            hashtable.at(hash).push_back(atoi(word));         

        if ( atoi(word) == -1)

            l=0;         

        else

            l++;

    }

    // Init the start

    hashtable.at(0).push_back(1);

    hashtable.at(0).push_back(-1);                             

}

/********************END HASH FUNCTION*******************************/

/********************  EXPLORE FUNCTION  ****************************/

/*Explore the Maze*/

void ExploreMaze(vector< vector <int> > maze, queue<int> explore, vector <int> &pred)

{   

    vector<int> tempVector;

    int location;

    int forward;    

    char number[5];

    

    while (!explore.empty())

    {    

        location = explore.front();

        explore.pop();

        forward = explore.front();

        explore.pop();

        if (pred[forward]==-1)

            pred[forward]=location;

        tempVector=maze[forward];

        int l=0;        

        while(tempVector[l]!=-1)

        {

            explore.push(forward);

            explore.push(tempVector[l]);

            l++;

        }         

    }        

}

/********************END EXPLORE FUNCTION****************************/

/**********************  ROUT FUNCTION  *****************************/

/*Rout the Maze*/

void RoutMaze(stack<int> &rout, vector <int> &pred)

{   

    int location = MAZE_SIZE-1;

    rout.push(MAZE_SIZE-1);    

    while(location!=1)

    {

        rout.push(pred[location]);

        location=pred[location];

    }        

}

/**********************END ROUT FUNCTION*****************************/    

/********************  MAIN FUNCTION   ******************************/

int main(int argc, char *argv[])

{

    vector < vector <int> > maze((size_t) MAZE_SIZE);

    vector <int> pred;

    vector<int> tempVector;    

    queue<int> explore;

    stack<int> rout;     

    char MazeFile[]="maze.txt";



    // Init the pred-vector

    for (int i=0; i < MAZE_SIZE; i++)

         pred.push_back(-1);

    // Create the Maze from file              

    Hash(maze, MazeFile);



    // Init the queue

    explore.push(0);

    explore.push(1);

    // Explore the Maze

    cout << "Exploring the Maze\n";

	cout << "this might take a second\n\n";    

    ExploreMaze(maze, explore, pred);

    // Populate the stack             

    RoutMaze(rout, pred);

    // Print the rout

    PrintRout(rout);

                        

    system("PAUSE");

    return 0;

}

/********************END MAIN FUNCTION******************************/