/**********************************
 **    File:       lemmings.c    **
 **    Programmer: Marc Douet    **
 **    Date:       07/21/02      **
 **********************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LASER_LEFT	0	/* Tells when a laser is firing left.	*/	
#define LASER_UP		1	/* Tells when a laser is firing up.		*/
#define LASER_RIGHT	2	/* Tells when a laser is firing right.	*/
#define LASER_DOWN	3	/* Tells when a laser is firing down.	*/
#define MAX_DIM		10	/* Max Dimension of the game board.		*/
#define MIN_DIM		1	/* Min Dimension of the game board.		*/
#define TRUE		1	/* Macro for boolean true.			*/
#define FALSE		0	/* Macro for boolean false.			*/


/* Struct to represent an (x,y) coordinate.	*/
typedef struct Coordinate {
	int x;
	int y;
} coordinate_t;


/**********************
 ** Global Variables **
 **********************/
coordinate_t	maxBoardPos;				/* The max x,y board values.	*/
coordinate_t	lemmingPos;					/* Position of the Lemming.	*/
coordinate_t	laserPos[(MAX_DIM*MAX_DIM)-MAX_DIM];/* Array of laser positions.	*/	
coordinate_t	grassPos[MAX_DIM];			/* Array of grass positions.	*/
coordinate_t	lavaPos[MAX_DIM];				/* Array of lava positions.	*/
char			gameBoard[MAX_DIM][MAX_DIM];		/* The game board matrix.	*/
int			numLasers;					/* Number of lasers.		*/
int			numGrassPatches;				/* Number of grass patches.	*/
int			numLavaPits;				/* Number of lava pits.		*/
	

/***************************************************************************
 * Function:  initGlobals
 *
 * Synopsis:  void initGlobals(void)
 *
 * Description:  Initializes all global arrays and variables.
 * 		     		
 * Return Value:  None.
 ***************************************************************************/ 
void initGlobals()
{
	int row, col;

	/* Initialize all grass and lava positions to -1.	*/
	for(row = 0; row < MAX_DIM; row++) {
		grassPos[row].x = grassPos[row].y = -1;
		lavaPos[row].x = lavaPos[row].y = -1;
	}

	/* Initialize all laser positions to -1			*/
	for(row = 0; row < ((MAX_DIM*MAX_DIM)-MAX_DIM); row++)
		laserPos[row].x = laserPos[row].y = -1;

	/* Initialize the game board matrix to NULL.		*/
	for(row = 0; row < MAX_DIM; row++)
		for(col = 0; col < MAX_DIM; col++)
			gameBoard[row][col] = '\0';

	/* Initialize all element counts to 0.			*/
	numLasers = numGrassPatches = numLavaPits = 0;
}


/***************************************************************************
 * Function:  clearBuffer
 *
 * Synopsis:  void clearBuffer(char *buf)
 *
 *	        buf  [IN/OUT]  The buffer to be cleared out.
 *
 * Description:  Clears out the specified buffer.
 * 		     		
 * Return Value:  None.
 ***************************************************************************/ 
void clearBuffer(char *buf)
{
	int index;

	/* Initialize the buffer to NULL.	*/
	for(index = 0; index < sizeof(buf); index++)
		buf[index] = '\0';	
}


/***************************************************************************
 * Function:  readGameBoard
 *
 * Synopsis:  void readGameBoard(void)
 *
 * Description:  Reads in the game board from input and stores it in
 *		     the game board matrix.
 * 		     		
 * Return Value:  None.
 ***************************************************************************/ 
void readGameBoard()
{
	int row;

	/* Read in every row of the board from input.	*/
	for(row = 0; row < maxBoardPos.y; row++) 
		scanf("%s", gameBoard[row]);
}


/***************************************************************************
 * Function:  setPositions
 *
 * Synopsis:  void setPositions(void)
 *
 * Description:  Sets the positions of the Lemming and all board objects.
 * 		     		
 * Return Value:  None.
 ***************************************************************************/ 
void setPositions()
{
	int row, col, lemmingCount = 0;

	/* Run through all board objects setting their cooresponding positions.	*/
	for(row = 0; row < maxBoardPos.y; row++)
		for(col = 0; col < maxBoardPos.x; col++) 
			switch(gameBoard[row][col]) {
				case 'L':	/* Set the position of the Lemming.		*/
					lemmingPos.x = col;
					lemmingPos.y = row;
					lemmingCount++;

					/* Ensure that there is only one Lemming.		*/
					if(lemmingCount > 1) {
					   printf("Error: There is more than one Lemming.\n");
					   exit(1);
					}

					/* Ensure the Lemming is on the first row.	*/
					if(lemmingPos.y != 0) {
					   printf("Error: Lemming must be on first row.\n");
					   exit(1);
					}
					break;

				case 'S':	/* Set the positions of all lasers.		*/
					laserPos[numLasers].x = col;
					laserPos[numLasers].y = row;
					numLasers++;

					/* Ensure the laser is not on the last row.	*/
					if(laserPos[numLasers-1].y == maxBoardPos.y-1) {
					   printf("Error: Laser found on the last row.\n");
					   exit(1);
					}					
					break;

				case 'P':	/* Set the positions of all lava pits.	*/
					lavaPos[numLavaPits].x = col;
					lavaPos[numLavaPits].y = row;
					numLavaPits++;

					/* Ensure the lava pit is on the last row.	*/
					if(lavaPos[numLavaPits-1].y != maxBoardPos.y-1) {
					   printf("Error: Lava pit not on last row.\n");
					   exit(1);
					}	
					break;

				case 'G':	/* Set the positions of all grass patches.*/
					grassPos[numGrassPatches].x = col;
					grassPos[numGrassPatches].y = row;
					numGrassPatches++;

					/* Ensure the grass patch is on the last row.	*/
					if(grassPos[numGrassPatches-1].y != maxBoardPos.y-1) {
					   printf("Error: Grass patch not on last row.\n");
					   exit(1);
					}	
					break;

				case 'O':	/* Empty space, so nothing to set.		*/
					break;

				default:	/* Bad object, print an error.		*/
					printf("Error: %c is not a valid game board object\n"
						,gameBoard[row][col]);
					exit(1);
			}		
}


/***************************************************************************
 * Function:  invalidPosition
 *
 * Synopsis:  int invalidPosition(void)
 *
 * Description:  Determines whether the current position of the Lemming
 *	           is actually on the game board.
 * 		     		
 * Return Value:  TRUE if the position is invalid, FALSE otherwise.
 ***************************************************************************/ 
int invalidPosition()
{
	/* Return 1 if the Lemming's x or y is less than 0, or greater than or	*/
	/* equal to the corresponding x,y max board positions; else return 0.	*/
	return ((lemmingPos.x < 0 || lemmingPos.x >= maxBoardPos.x)
		|| (lemmingPos.y < 0 || lemmingPos.y >= maxBoardPos.y));
}


/***************************************************************************
 * Function:  landedInLava
 *
 * Synopsis:  int landedInLava(void)
 *
 * Description:  Determines whether the current position of the Lemming
 *	           occupies a lava pit or not.
 * 		     		
 * Return Value:  TRUE if the Lemming landed in a lava pit, FALSE otherwise.
 ***************************************************************************/ 
int landedInLava()
{
	int index;

	/* For every lava pit position, compare the cooresponding x,y values.	*/
	for(index = 0; index < numLavaPits; index++)
		/* IF the positions match, return TRUE!					*/
		if(lemmingPos.x == lavaPos[index].x 
			&& lemmingPos.y == lavaPos[index].y)
				return TRUE;

	/* IF we got here, that means no match was found, so return FALSE.	*/
	return FALSE;
}


/***************************************************************************
 * Function:  landedOnGrass
 *
 * Synopsis:  int landedOnGrass(void)
 *
 * Description:  Determines whether the current position of the Lemming
 *	           occupies a grass patch or not.
 * 		     		
 * Return Value:  TRUE if the Lemming landed on a grass patch, FALSE 
 *		      otherwise.
 ***************************************************************************/ 
int landedOnGrass()
{
	int index;

	/* For every grass patch position, compare the cooresponding x,y values.*/
	for(index = 0; index < numGrassPatches; index++)
		/* IF the positions match, return TRUE!					*/
		if(lemmingPos.x == grassPos[index].x 
			&& lemmingPos.y == grassPos[index].y)
				return TRUE;

	/* IF we got here, that means no match was found, so return FALSE.	*/
	return FALSE;
}


/***************************************************************************
 * Function:  safeMove
 *
 * Synopsis:  int safeMove(int turn)
 *			  
 *            turn  [IN]  The current turn, used to determine the
 *		          direction of the laser.
 *
 * Description:  Determines whether this is a safe position for the 
 *	           Lemming to be at (won't get him killed).
 * 		     		
 * Return Value:  TRUE if this is a safe Lemming position, FALSE otherwise.
 ***************************************************************************/ 
int safeMove(int turn)
{
	int index;

	/* IF this is an invalid position, or our Lemming landed		*/
	/* in lava, he better go back, return FALSE.				*/
	if(invalidPosition() || landedInLava())
		return FALSE;

	/* Mod the turn by 4 to get the direction of the laser,		*/
	/* then given all laser trajectories, determine if this is		*/
	/* a safe move to make (one that won't kill our Lemming).		*/
	switch(turn%4) {

		case LASER_UP:		/* The laser is firing upwards.	*/
			for(index = 0; index < numLasers; index++)
				if((lemmingPos.x == laserPos[index].x)
					&& (lemmingPos.y <= laserPos[index].y)) 
					return FALSE;
			break;

		case LASER_RIGHT:	/* The laser is firing to the right.	*/
			for(index = 0; index < numLasers; index++)
				if((lemmingPos.y == laserPos[index].y)
					&& (lemmingPos.x >= laserPos[index].x))
					return FALSE;
			break;

		case LASER_DOWN:	/* The laser is firing downward.		*/
			for(index = 0; index < numLasers; index++)
				if((lemmingPos.x == laserPos[index].x)
					&& (lemmingPos.y >= laserPos[index].y))
					return FALSE;
			break;

		case LASER_LEFT:	/* The laser is firing to the left.		*/
			for(index = 0; index < numLasers; index++)
				if((lemmingPos.y == laserPos[index].y)
					&& (lemmingPos.x <= laserPos[index].x))
					return FALSE;
			break;

		default:		/* Not a valid laser trajectory.		*/
			printf("Error: %d is not a valid Laser Direction.\n",turn%4);
			return FALSE;
	}

	/* IF we got here, we survived this move, so return TRUE!		*/
	return TRUE;
}


/***************************************************************************
 * Function:  moveLemmingLeft
 *
 * Synopsis:  int moveLemmingLeft(int turn)
 *			  
 *            turn  [IN]  The current turn, used to determine move safety.
 *
 * Description:  Moves the Lemming one space to the left and one space 
 *	           down, determining whether each move is safe, backing 
 *		     up to its initial position if either move results in death.
 * 		     		
 * Return Value:  TRUE if the Lemming survived the moves, FALSE if he died. 
 *                In the case of death, the Lemming's position is reset.
 ***************************************************************************/ 
int moveLemmingLeft(int turn)
{
	/* Move the Lemming one space to the left.					*/
	lemmingPos.x--;

	/* IF the Lemming got killed as a result, back up and return FALSE.	*/
	if(!safeMove(turn)) {
		lemmingPos.x++;
		return FALSE;
	}

	/* The Lemming has survived so far, so now move him one space down.	*/
	lemmingPos.y++;

	/* IF the Lemming got killed as a result, back up and return FALSE.	*/
	if(!safeMove(turn)) {
		lemmingPos.y--;
		lemmingPos.x++;
		return FALSE;
	}

	/* The Lemming survived the Left/Down move, so return TRUE!			*/
	return TRUE;
}


/***************************************************************************
 * Function:  moveLemmingDown
 *
 * Synopsis:  int moveLemmingDown(int turn)
 *			  
 *            turn  [IN]  The current turn, used to determine move safety.
 *
 * Description:  Moves the Lemming one space down, determining whether the
 *               move is safe, backing up to its initial position if the
 *               move results in death.
 * 		     		
 * Return Value:  TRUE if the Lemming survived the move, FALSE if he died. 
 *                In the case of death, the Lemming's position is reset.
 ***************************************************************************/
int moveLemmingDown(int turn)
{
	/* Move the Lemming one space down.							*/
	lemmingPos.y++;

	/* IF the Lemming got killed as a result, back up and return FALSE.	*/
	if(!safeMove(turn)) {
		lemmingPos.y--;
		return FALSE;
	}

	/* The Lemming survived the Down move, so return TRUE!			*/
	return TRUE;
}


/***************************************************************************
 * Function:  moveLemmingRight
 *
 * Synopsis:  int moveLemmingRight(int turn)
 *			  
 *            turn  [IN]  The current turn, used to determine move safety.
 *
 * Description:  Moves the Lemming one space to the right and one space 
 *	           down, determining whether each move is safe, backing 
 *		     up to its initial position if either move results in death.
 * 		     		
 * Return Value:  TRUE if the Lemming survived the moves, FALSE if he died. 
 *                In the case of death, the Lemming's position is reset.
 ***************************************************************************/ 
int moveLemmingRight(int turn)
{
	/* Move the Lemming one space to the right.					*/
	lemmingPos.x++;

	/* IF the Lemming got killed as a result, back up and return FALSE.	*/
	if(!safeMove(turn)) {
		lemmingPos.x--;
		return FALSE;
	}

	/* The Lemming has survived so far, so now move him one space down.	*/
	lemmingPos.y++;

	/* IF the Lemming got killed as a result, back up and return FALSE.	*/
	if(!safeMove(turn)) {
		lemmingPos.y--;
		lemmingPos.x--;
		return FALSE;
	}

	/* The Lemming survived the Right/Down move, so return TRUE!		*/
	return TRUE;
}


/***************************************************************************
 * Function:  moveLemming
 *
 * Synopsis:  int moveLemming(int turn)
 *			  
 *            turn  [IN]  The current turn, used to determine move safety.
 *
 * Description:  Tries to reach a patch of grass by recursively calling 
 *	           itself, trying each possible move in the following order:
 *               LEFT/DOWN, DOWN, RIGHT/DOWN, returning FALSE if the move
 *               killed the Lemming, or TRUE if he survived the move or
 *               reached a grass patch.  This is an exhaustive search for 
 *               a safe path to a grass patch, in other words every possible
 *               move is tried until either the Lemming lands on a grass
 *               patch, or there are no un-tried moves remaining (the Lemming 
 *               died trying).  Of course one could keep track of all un-
 *               successful moves, recording the position and turn that caused
 *               death, and avoiding those positions at that turn, but given
 *               that the largest number of moves is 9, there is no need to 
 *               trim the search tree.
 * 		     		
 * Return Value:  TRUE if the Lemming landed on a patch of grass or has
 *                survived a move, or FALSE if a move resulted in death.
 ***************************************************************************/ 
int moveLemming(int turn)
{
	/* Save the current state of the Lemming's Position in case		*/
	/* he needs to backtrack after a deadly move.				*/
	coordinate_t tempLemmingPos;	
	tempLemmingPos.x = lemmingPos.x;
	tempLemmingPos.y = lemmingPos.y;

	/* Let's start this turn by incrementing the turn counter.		*/
	turn++;

	/* Base Case - IF our Lemming landed on grass, return TRUE!		*/
	if(landedOnGrass())
		return TRUE;

	/* IF we are hit by the laser before moving, return false.		*/
	if(!safeMove(turn)) 
		return FALSE;

	/* IF our Lemming moves Left/Down and lives, continue moving.	*/
	if(moveLemmingLeft(turn)) 
		/* IF the Lemming reached a grass patch, return TRUE.		*/
		if(moveLemming(turn)) 
			return TRUE;

	/* Our Lemming didn't survive the Left/Down move, so restore	*/
	/* the previous state of the Lemming's postion.				*/
	lemmingPos.x = tempLemmingPos.x;
	lemmingPos.y = tempLemmingPos.y;
       
	/* IF our Lemming moves Down and lives, continue moving.		*/
	if(moveLemmingDown(turn)) 
		/* IF the Lemming reached a grass patch, return TRUE.		*/
		if(moveLemming(turn)) 
			return TRUE;

	/* Our Lemming didn't survive the Down move, so restore the		*/
	/* previous state of the Lemming's postion.				*/
	lemmingPos.x = tempLemmingPos.x;
	lemmingPos.y = tempLemmingPos.y;
	
	/* IF our Lemming moves Right/Down and lives, continue moving.	*/
	if(moveLemmingRight(turn)) 
		/* IF the Lemming reached a grass patch, return TRUE.		*/
		if(moveLemming(turn)) 
			return TRUE;
			
	/* Our Lemming didn't survive the Right/Down move, so restore	*/
	/* the previous state of the Lemming's postion.				*/
	lemmingPos.x = tempLemmingPos.x;
	lemmingPos.y = tempLemmingPos.y;

	/* This was a bad move, our poor Lemming is toast, return FALSE!	*/
	return FALSE;
}


/***************************************************************************
 * Function:  main
 *
 * Synopsis:  int main(void)
 *
 * Description:  Main driver of the program.  Trys to read the START tag
 *               from input.  If a START tag was found goes into a loop that 
 *               through each iteration:
 *		 	1.  Reads in the game board matrix
 *			2.  Sets the position of the Lemming and each board object.
 *			3.  Calls moveLemming() with 0, to recursively move the 
 *			    Lemming until either reaching a patch of grass, or
 *			    running out of paths (every path results in death).
 *			4.  Prints out FERRET for success or GARRET for failure.
 *			5.  If another "START" string exists, continue.
 *			6.  If another "START" string does not exist,
 *			    break out of the loop and exit.
 *
 * Return Value:  0 if success, 1 if error was encountered.
 ***************************************************************************/ 
void main()
{
	char	tag[sizeof("START")];
	int	rowDim, colDim;

	/* Initialize the tag and board dimensions.				*/
	clearBuffer(tag);
	rowDim = colDim = 0;
	maxBoardPos.x = maxBoardPos.y = 0;
	
	/* Read in the START tag and board dimensions.				*/
	scanf("%s %d %d", tag, &colDim, &rowDim);
	maxBoardPos.x = colDim;
	maxBoardPos.y = rowDim;

	/* WHILE we have found a START tag...					*/
	while(!strcmp(tag, "START")) {
		/* Ensure that the row and column dimensions are valid.	*/
		if((maxBoardPos.x < MIN_DIM || maxBoardPos.x > MAX_DIM)
			|| (maxBoardPos.y < MIN_DIM || maxBoardPos.y > MAX_DIM)) {
			printf("Error: the dimensions of the board are invalid\n");
			exit(1);
		}

		/* Initialize all global variables.					*/
		initGlobals();

		/* Try to read in the game board from input.			*/
		readGameBoard();

		/* Clear out the START/END tag to read in the END tag.	*/
        	clearBuffer(tag);
 
        	/* Read in the END tag. 						*/
        	scanf("%s", tag);  

		/* IF an END tag was not found, print an error, and exit 1. */
		if(strcmp(tag, "END")) {
			printf("Error: No END tag was found after the data..\n");
			exit(1);
		}

		/* Use game board to set the Lemming and object positions.	*/
		setPositions();

		/* Determine whether the Lemming can reach the grass, and	*/
		/* print the result (FERRET=LIVED, GARRET=DIED).		*/
		if(moveLemming(0))
			printf("FERRET\n");
		else  printf("GARRET\n");

		/* Clear the START/END tag and board dimensions.		*/
		clearBuffer(tag);
		rowDim = colDim = 0;
		maxBoardPos.x = maxBoardPos.y = 0;

		/* Try to read in another tag and board dimensions.		*/
		scanf("%s %d %d", tag, &colDim, &rowDim);
		maxBoardPos.x = colDim;
		maxBoardPos.y = rowDim;
	}
	
	/* We are done with all data sets, so exit 0.				*/
	exit(0);
}