#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <process.h>

using namespace std;
int MyF( int );

int mazeSolver(int i, int j);
struct maze
{
	int rows;
	int cols;
	char matrix [100][100];
};

maze myMaze;

int main()
{
	
	//required variables
	ifstream in;
	in.open("CMMmaze1.txt");
	char line;

	//read the matrix
	in >> myMaze.rows;
	in >> line;
	in >> myMaze.cols;
	cout << "Reading a " << myMaze.rows << " by " << myMaze.cols << " matrix." << endl;
	//read in end of line character
	in.get(line);
	for(int i=0; i<myMaze.rows; i++)
	{
		for(int j=0; j<myMaze.cols; j++)
		{
			in.get( myMaze.matrix[i][j] );
		}
		//Burn the end of line character
		in.get(line);
	}

	int startRow;
	int startCol;
	//Find start
	for(int i=0; i<myMaze.rows; i++)
		for(int j=0; j<myMaze.cols; j++)
			if( myMaze.matrix[i][j] == 's' || myMaze.matrix[i][j] == 'S')	
			{
				startRow = i;
				startCol = j;
			}

	//Call mazeSolver
	mazeSolver(startRow,startCol);

	//Print maze
	for(int i=0; i<myMaze.rows; i++)
	{
		for(int j=0; j<myMaze.cols; j++)
			cout << myMaze.matrix[i][j];
		cout << endl;
	}

	return 0;
}

//Assumptions
	//Bordered by *
	//Valid S-F path
	//Visit a position once
//recursively checks all four paths (N,S,E,W) for an open space
//returns the length of the path or -1 if not found
int mazeSolver(int i, int j)
{
	//check neighbors for 'F'
	if(myMaze.matrix[i-1][j] == 'F' ||	//N
		myMaze.matrix[i][j+1] == 'F' ||	//E
		myMaze.matrix[i+1][j] == 'F' ||	//S
		myMaze.matrix[i][j-1] == 'F')	//W
	{	
		//return 0 for the length
		myMaze.matrix[i][j] = 'X';
		cout << "Finished" << endl;
		return 0;
	}

	//north path
	//(i-1,j)
	//check if valid/open
	if(myMaze.matrix[i-1][j] == ' ')
	{
		//call mazeSolver(north)
		int NorthPath = mazeSolver(i-1, j);
		if(NorthPath >-1)
		{
			return 0;
		}
	}
	//south path
	//(i+1,j)
		//...
	//east path
	//(i,j+1)
		//...
	//west path
	//(i,j-1)
		//...
	//return no paths (-1)
	return -1;
}