// lPathfinder.cpp : Defines the entry mPoint for the console application.
//
#include "stdafx.h"
#include<stdio.h>
#include<list>
#include<stdlib.h>
#define n 5
#define m 4
struct mPoint
{
	int x,y;
};  //Describes a Coordinate.
typedef int pMap[n][m]; //creates a map
typedef std::list<mPoint> lPath; // a single successful path from start to end
typedef std::list<lPath> lPaths; // a list of all successful paths
mPoint makeP(int x, int y); // Groups two values x and y to a single point
bool pCompare(mPoint a, mPoint b); //compares two points for equality. Returns true if the points are the same, false if not.
//void mPrint(pMap mp, lPath c); Not used
lPaths final;
void Pathfinder(mPoint stop, pMap mp, lPath current, mPoint loc) // Takes as parameters two points, stop(end point) and loc that serves as the relative start point, our map and the current path(empty on first call)
{
	if (mp[loc.x][loc.y]==0) //Checking the course isnt started as a obstacle(0) point.
	{
		printf("**Error! You cannot start the path in a cell containing a '0'**\n");
		return;
	}
	current.push_back(loc); //saves current point
	mp[loc.x][loc.y]=2; //marks current point as passed-through
	if (pCompare(stop,loc)) //checks if we've reached target point.
	{
		printf("**(%d,%d) - We are in stop point (%d,%d) Path Found! Adding to list of successful paths and starting over.\n",loc.x,loc.y,stop.x,stop.y);
		final.push_front(current);
		return;
	}
	//right direction
	if (loc.y<m-1)
	{
		if(mp[loc.x][loc.y+1]==1)
		{
			printf("**(%d,%d) Going Right >> !**\n",loc.x,loc.y);
			Pathfinder(stop,mp,current,makeP(loc.x,loc.y+1));
		}
	}
	//left
	if (loc.y>0)
	{
		if(mp[loc.x][loc.y-1]==1)
		{
			printf("**(%d,%d) Going Left << !**\n",loc.x,loc.y);
			Pathfinder(stop,mp,current,makeP(loc.x,loc.y-1));
		}
	}
	//down
	if (loc.x<n-1)
	{
		if(mp[loc.x+1][loc.y]==1)
		{
			printf("**(%d,%d) Going Down vv !**\n",loc.x,loc.y);
			Pathfinder(stop,mp,current,makeP(loc.x+1,loc.y));
		}
	}
	//up
	if (loc.x>0)
	{
		if(mp[loc.x-1][loc.y]==1)
		{
			printf("**(%d,%d) Going Up ^^ !**\n",loc.x,loc.y); 
			Pathfinder(stop,mp,current,makeP(loc.x-1,loc.y));
		}
	}
	return;
}
int _tmain(int argc, _TCHAR* argv[])
{
	int mp[5][4] = { { 1 , 0 , 0 , 0  } ,
				 { 0 , 1 , 0 , 1  } ,
			         { 1 , 1 , 1 , 1  } ,
			         { 1 , 1 , 1 , 1   } ,
			         { 0 , 1 , 0 , 0  } };
	lPath c;
	mPoint sl = makeP(1,1);
	mPoint e = makeP(3,3);
	mPoint temp;
	Pathfinder(e,mp,c,sl);
	while(!final.empty())
	{
		printf("------------------------------\nPath:\n");
		c=final.front();
		final.pop_front();
		while(!c.empty())
		{
			temp=c.front();
			c.pop_front();
			printf("(%d,%d)\n",temp.x,temp.y);
		}
		//mPrint(mp,c); Not used
		printf("End Path\n------------------------------");
		
	}
	system("PAUSE > NUL");
	return 0;
}
mPoint makeP(int x, int y)
{
	mPoint p;
	p.x=x;
	p.y=y;
	return p;
}
bool pCompare(mPoint a, mPoint b)
{
	return (bool)((a.x==b.x)&&(a.y==b.y));
}