2001 LSU Computer Science High School Programming Contest

Sponsored by Texas Instruments

Veteran - Problem 5

Treasure Maps

Problem: Dr Brownian was searching through his attic looking for old reasearch projects. And he stumbled upon a chest given to him by his great aunt that had several old papers inside. These manuscripts had several X's and long list of numbers on the paper which could only mean one thing, lots of treasure. The maps gave explict instructions on where to go and warned not to deviate off the path.

As Dr. Brownian goes off in search of treasure he finds coins and small valuable rocks. But he also has some hardships which he must sacrifice some of his holding to survive. If Dr. Brownian ever deviates from the map he will get lost and die of starvation or be eaten by a miscellaneous hungry animal.

Problem Explanation: You will process the instructions from the maps and determine which maps are good and how much wealth to expect. All information will be provided one number per line. The maximum map size will be 9 x 9 with the botom lefthand (south west) corner being [1,1]. As you pass though squares (make steps), you encounter treasure and troubles (represented as numerical values, troubles will have negative values). Your job is to output the number of squares you visit and the final wealth if the map works. If it does not work (you step out of bounds, you don't reach the goal) you output Bad Map.

Input:

The first number will be the number of maps to process. This will be followed by the data for one map which followed by the data for the next map, etc. Each map data section will start with the number of rows and the number of columns in the map. The next data items will be the actual values of the various map locations ([1,1], [1,2], ... [2,1], ... Next will be the begining row and column followed by the ending row and column. Next will be the number of moves followed by each move (a direction and a distance). The table below explains how the directions are encoded (what numbers mean what directions).

Number Direction
8 North
6 East
2 South
4 West

As you go through the directions add the valuables on the square to what you are carrying and remove the value from that square (once visited, the wealth/disaster has been consumed).

Output: Your are to output how many squares were visited followed by the total wealth accumulated. If the map is invalid, output Bad Map instead of the two numeric values.

Sample Input:

2		number of maps
2		number of rows  -- starting first map
3		number of columns
1		map [1,1] - bottom/south lefthand/west corner
-2		map [1,2]
3		map [1,3]
5		map [2,1]
4		map [2,2]
-1		map [2,3]
1		begining row
2		begining column
1		ending row
3		ending column
3		number of moves
4		direction
1		number of steps
8		direction
1		number of steps
6		direction
1		number of steps
3		number of rows  -- starting second map
3		number of columns
2		map [1,1] - bottom/south lefthand/west corner
4		map [1,2]
-8		map [1,3]
10		map [2,1]
5		map [2,2]
7		map [2,3]
9		map [3,1]
3		map [3,2]
-1		map [3,3]
2		begining row
3		begining column
2		ending row
1		ending column
4		number of moves
2		direction
1		number of steps
4		direction
1		number of steps
8		direction
1		number of steps
4		direction
1		number of steps

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

Sample Output:

Bad Map
5   18


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