South Central USA Regional Programming Contest

Problem #4: Frogger's For Dinner

 
Introduction

"Uncle Jacques, " you ask, "What's for dinner?"

"Ask me again in 10 minutes, " Uncle Jacques replies, eyeing the weary-looking frog sitting on the shoulder of Interstate 10, in front of your dilapidated shack.

You notice the potential roadkill as it begins its journey across the vehicle-laden road. You want to know if you should begin boiling a pot of water in anticipation of frog legs for dinner or warm up the leftover possum. You fire up your Swamp 'Puter XL2 and quickly write a program to determine if it is possible for the frog to make it across the road or if it will be hit by a vehicle.

Examining the patch of road in front of your shack, you notice the lanes and shoulders resemble a 10 X 10 grid of squares (shown below). You also notice that the way the frog and the vehicles are moving can be described in "turns". To determine if the frog makes it across the road, you quickly devise a set of rules:

  1. At the onset of a run, the frog can start in any square on row 0 (the starting shoulder).
  2. At the onset of a run, each vehicle will occupy a square in any column, but only in rows 1-8 (the lanes).
  3. Each turn will consist of two steps:
  4. The frog will succeed in crossing the interstate for a run if it can reach row 9 (without becoming roadkill) after a series of turns starting in ANY column on row 0 (he's not the dumbest frog in the world, either).
  5. The frog will become roadkill if at any point it occupies the same square as a vehicle. This includes:

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will describe the starting conditions of the interstate for a run and will be formatted according to the following description. There will be no blank lines separating data sets.

  1. Start line - A single line, "START"
  2. The next 8 lines will represent rows 1-8 (the "lanes" of the interstate), starting with row 1. Each line will consist of 10 integers, separated by single spaces. Each integer will represent a column for that row and will be either:
  3. End line - A single line, "END"

Output

Output for each data set will be exactly one line of output. The line will either be "LEFTOVER POSSUM" or "FROGGER" (both all caps with no whitespace leading or following).

"LEFTOVER POSSUM" will appear if the frog can make it safely (without becoming roadkill) across the interstate after a series of turns starting in ANY column on row 0.

"FROGGER" will be output for a data set if it fails to meet the criteria for a "LEFTOVER POSSUM" line.

Sample Input

START
3 0 0 0 0 3 0 0 0 3
1 0 0 0 1 0 0 0 0 0
4 0 0 0 0 0 0 4 0 0
0 0 2 0 0 0 0 0 0 2
5 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 2 0 2
0 0 0 4 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0
END
START
9 9 9 9 9 9 9 9 9 9
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
END
START
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
END
Sample Output
FROGGER
FROGGER
LEFTOVER POSSUM


The statements and opinions included in these pages are those of 2001 South Central USA Regional Programming Contest Staff only. Any statements and opinions included in these pages are NOT those of Louisiana State University, LSU Computer Science, LSU Computing Services, or the LSU Board of Supervisors.
© 1999,2000,2001 Isaac W. Traxler