#include <stdio.h>

#define MAX 200

//robot and maze variables and arrays
char maze[20][20]; 		//[vertical][horizontal]
int curVpos = 0, curHpos = 0; 	//current position

//stack variables and arrays
int counter = 0;
int vstack[MAX];	//vertical position stack
int hstack[MAX];	//horizontal position stack

//function prototypes
void getvals();
void find_S(int * curVpos, int * curHpos);
int scan(int * curVpos, int * curHpos);
void push (int * curVpos, int * curHpos, int * counter);
void pop(int * curVpos, int * curHpos, int * counter);
int go_right(int * curVpos, int * curHpos);
int go_up(int * curVpos, int * curHpos);
int go_left(int * curVpos, int * curHpos);
int go_down(int * curVpos, int * curHpos);

//file pointers
FILE *ifp, *ofp;

int main(void)
	{
	int numopts, i, j, k = 0;
	char filename[13]; //temp file name string
	
	//get filenames and assign pointers
	printf("\nEnter the name of the maze file.\n");
	scanf("%s", filename);
	ifp = fopen(filename, "r");
	printf("\nEnter the name of the output file.\n");
	scanf("%s", filename);
	ofp = fopen(filename, "w");
	
	printf("\nOrder of visiting: Right Up Left Down\n");
	
	getvals();
	
	find_S(&curVpos, &curHpos);
	
	//while the current position does not equal 'G'; keep moving
	while (maze[curVpos][curHpos] != 'G')
		{
		k++;
		if (k > 1000)
			break;
		
		numopts = scan(&curVpos, &curHpos);
		
		//if there is more than one option, push this position to stack
		if (numopts > 1)
			push(&curVpos, &curHpos, &counter);
		
		if (numopts >= 1)
			{
			if ((go_right(&curVpos, &curHpos)) == 1)
				continue;
			if ((go_up(&curVpos, &curHpos)) == 1)
				continue;
			if ((go_left(&curVpos, &curHpos)) == 1)
				continue;
			if ((go_down(&curVpos, &curHpos)) == 1)
				continue;
			}
		
		//if there are no options, pop a position off the stack
		if (numopts == 0)
			pop(&curVpos, &curHpos, &counter);
		
		} // end while ()
	
	//print processed maze
	printf("\nThe Processed maze\n");
	for (i = 0; i < 20; i++)
		{
		printf("\n");
		for (j = 0; j < 20; j++)
			printf("%c", maze[i][j]); //end for (j)

		}
	
	fclose(ifp);
	fclose(ofp);
	
	} // end main()


//read maze from file into an array

void getvals()
	{
	int i, j;
	char tempstring[23];
	
	for (i = 0; i < 20; i++)
		{
		fgets(tempstring, 22, ifp);
		for (j = 0; j < 20; j++)
			{
			maze[i][j] = tempstring[j];
			} // end for (j)
		} // end for (i)
	} //end getvals()

//find "S" and set it as the current position
void find_S(int *curVpos, int *curHpos)
	{
	int i, j;
	for (i = 0; i < 20; i++)
		for (j = 0; j < 20; j++)
			if (maze[i][j] == 'S' || maze[i][j] == 's')
				{
				*curVpos = i;
				*curHpos = j;
				i = 20;
				j = 20;
				} // end if (maze)
	} // end find_S()

//scans surrounding cells and returns # of options
int scan(int *curVpos, int *curHpos)
	{
	int numopts = 0;
	if (maze[*curVpos][*curHpos + 1] == '0')	//right
		numopts++;
	if (maze[*curVpos - 1][*curHpos] == '0')	//up
		numopts++;
	if (maze[*curVpos][*curHpos - 1] == '0')	//left
		numopts++;
	if (maze[*curVpos + 1][*curHpos] == '0')	//down
		numopts++;
	return numopts;
	} // end scan()

void push(int * curVpos, int * curHpos, int * counter)
	{
	vstack[*counter] = *curVpos;
	hstack[*counter] = *curHpos;
	*counter++;
	printf("\npush%d", *counter);
	} //end push()

void pop(int * curVpos, int * curHpos, int * counter)
	{
	counter--;
	if (counter<0)
		{
		printf("Stack underflow.\n");
		return;
		}
	*curVpos = vstack[*counter];
	*curHpos = hstack[*counter];
	} //end pop()

//if going RIGHT is possible, do so and return 1, otherwise return 0
int go_right(int * curVpos, int * curHpos)
	{
	if (maze[*curVpos][*curHpos + 1] == '0' ||
	    maze[*curVpos][*curHpos + 1] == 'G')
		{
		fprintf(ofp, "%d %d\n", *curVpos, *curHpos);
		maze[*curVpos][*curHpos + 1] = 'v';
		*curHpos = *curHpos + 1;
		return 1;
		}
	else
		return 0;
	} // end go_right()


//if going UP is possible, do so and return 1, otherwise return 0
int go_up(int * curVpos, int * curHpos)
	{
	if (maze[*curVpos - 1][*curHpos] == '0' ||
	    maze[*curVpos - 1][*curHpos] == 'G')
		{
		fprintf(ofp, "%d %d\n", *curVpos, *curHpos);
		maze[*curVpos - 1][*curHpos] = 'v';
		*curVpos = *curVpos - 1;
		return 1;
		}
	else
		return 0;
	} // end go_up()

//if going LEFT is possible, do so and return 1, otherwise return 0
int go_left(int * curVpos, int * curHpos)
	{
	if (maze[*curVpos][*curHpos - 1] == '0' ||
	    maze[*curVpos][*curHpos - 1] == 'G')
		{
		fprintf(ofp, "%d %d\n", *curVpos, *curHpos);
		maze[*curVpos][*curHpos - 1] = 'v';
		*curHpos = *curHpos - 1;
		return 1;
		}
	else
		return 0;
	} // end go_left()

//if going DOWN is possible, do so and return 1, otherwise return 0
int go_down(int * curVpos, int * curHpos)
	{
	if (maze[*curVpos + 1][*curHpos] == '0' ||
	    maze[*curVpos + 1][*curHpos] == 'G')
		{
		fprintf(ofp, "%d %d\n", *curVpos, *curHpos);
		maze[*curVpos + 1][*curHpos] = 'v';
		*curHpos = *curHpos + 1;
		return 1;
		}
	else
		return 0;
	} // end go_down()