2001 LSU Computer Science High School Programming Contest

Sponsored by Texas Instruments

Novice and Veteran - Problem 3

A Muddle of Maps

Problem: At a recent estate sale of a renouned eccentric treasure hunter, Vincent Rapiere, you managed to be the highest bidder on a rusted antique trunk. The trunk's lid was stuck and could not be opened without damaging its value as an antique, so the auctioneer instead hyped the 'mystery' of the trunk. During the process of moving it to your house, however, the movers dropped it and damaged the lid. Now that the lid was beyond repair and antique value was severly lessened, you allow your curiousity to get the best of you.

That evening, you decide to open the trunk and remove the contents carefully. Inside you find a multitude of folded papers which appear to be maps. Your mind begins to reel. The estate sale was held because, although Vincent Rapiere was supposed to be the richest man on earth, he died penniless, with no indication of what became of his money.

He must have hidden it much the same way he found it! Here before you is a chest of maps some of which - perhaps all of which - could lead you to untold riches! The only question is whether they are real maps or fake maps. Or, specifically, which are which. After reading through one of Vincent's diaries (another little item you picked up at the estate sale), you have concluded the following:

If Vincent Rapiere was to make treasure maps like these, there would always be an indicated 'Start' point. Also, the (1,1) location of Vincent's maps always are located at the bottom lefthand corner of the map. The directions given would be written on the map and would correspond to scaled directions to be traveled on the map. Following the directions on the map should never take you outide of the boundaries of the map. The directions would lead you to the Target destination EXACTLY. If these conditions are not met, the map is a fake that Vincent made to add to the confusion.

Your task is to write a program that will analyze the maps and determine which ones (if any) are true treasure maps. A programmer friend of yours has already translated all of the maps into a data file in exchange for a (small) slice of the action if something comes of the maps. All YOU have to do is write the program to process the data. (Your friend doesn't know anything about treasure hunting, so you felt it would be best if YOU handle that part.)

Input: All input will be one value per line. The first number in the input file will be the number of maps to be processed. This number will be beween 1 and 9999. Following that will be the data for each map (one after the other). The first item in the map data is the number of rows in the map. That is followed by the number of columns. Next comes the starting row followed by the starting column. Next comes the ending row followed by the ending column. The next number is the number of moves to make. after that will be a pair of numbers for each move (the direction followed by how many steps). For example, a 6 followed by a 10 would mean that you should travel East 10 steps. The chart below will help you decode the numeric direction:

NumberDirection
8Up/North
6Right/East
2Down/South
4Left/West

Output: For each bad map, print 'Bad Map'. For each good map print 'Good Map'. After all maps are processed, the number of good maps should be printed. (such as, '32 Good Maps detected.')

Sample Input:

3		number of maps
5		number of rows   --  starting first map
5		number of columns
1		starting row
1		starting column
5		ending row
5		ending column
2		number of moves
8		direction
4		number of steps
6		direction
4		number of steps
20		number of rows   --  starting second map
10		number of columns
5		starting row
5		starting column
3		ending row
8		ending column
1		number of moves
4		direction
10		number of steps
4		number of rows   --  starting third map
5		number of columns
1		starting row
1		starting column
2		ending row
2		ending column
10		number of moves
8		direction
1		number of steps
6		direction
1		number of steps
2		direction
1		number of steps
6		direction
1		number of steps
8		direction
1		number of steps
6		direction
1		number of steps
8		direction
2		number of steps
4		direction
3		number of steps
2		direction
2		number of steps
6		direction
1		number of steps

Note: The items in italics are here to help you understand the data. Your real input will only have numbers.

Sample Output:

Good Map
Bad Map
Good Map
2 Good Maps detected.


Return to Problem Index


 

The statements and opinions included in these pages are those of 2001 LSU Computer Science High School Programming Contest only. Any statements and opinions included in these pages are not those of Louisiana State University or the LSU Board of Supervisors.
© 2000,2001 Isaac Traxler
Last modified: Friday, 01 July, 2011 16:24:51