// lPathfinder.cpp : Defines the entry mPoint for the console application.
//
#include "stdafx.h"
#include<stdio.h>
#include<list>
#define n 5
#define m 4
struct mPoint
{
	int x,y;
};  //Describes a Coordinate.
typedef int pMap[n][m]; //creates a map
typedef list<mPoint> lPath; // a single successful path from start to end
typedef 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.
lPaths final = new lPaths();
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 pCompare(loc,stop)
	{
		printf("Path found! Adding to list of final lPaths");
		final.push_back(current);
		return;
	}
	current.push_back(loc);
	m[loc.x][loc.y]=2;
	//up
	if ((loc.y>0))
		if (m[loc.x][(loc.y)-1]==1)
			Pathfinder(stop,mp,current,makeP(loc.x,loc.y-1));
	//down
	if ((loc.y<m-1))
		if (m[loc.x][(loc.y)+1]==1)
			Pathfinder(stop,mp,current,makeP(loc.x,loc.y+1))
	//right
	if ((loc.x<n-1))
		if (m[(loc.x)+1][loc.y]==1)
			Pathfinder(stop,mp,current,makeP(loc.x+1,loc.y))
	//left
	if ((loc.x>0))
		if (m[(loc.x)-1][loc.y]==1)
			Pathfinder(stop,mp,current,makeP(loc.x-1,loc.y))
}
int _tmain(int argc, _TCHAR* argv[])
{
	pMap mp = { { 1 , 0 , 0 , 0 , 1 } ,
			   { 0 , 1 , 0 , 1 , 1 } ,
			   { 1 , 1 , 1 , 1 , 1 } ,
			   { 0 , 1 , 0 , 0 , 1 } };
	lPath c;
	struct mPoint sl = makeP(1,2);
	struct mPoint e = makeP(3,1);
	struct mPoint temp;
	Pathfinder(e,mp,c,sl);
	while(!final.empty())
	{
		printf("------------------------------\nPath:");
		c=final.pop_front();
		while(!c.empty())
		{
			temp=c.pop_front();
			printf("(%d,%d)",temp.x,temp.y
		}
		printf("End Path\n------------------------------");
		
	}
	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));
}