1802: Magic Tower

Accplayer now falls in love with a flash game called “Magic Tower”. A hero is lost in the magic tower, which is filled with monsters and treasure. His goal is to reach the top floor and rescue the princess. Accplayer plays this game over and over again, but never succeeds. How complex the game is! Now he asks his best friend, you, to help him find out how to solve the puzzle. To simplify the problem, we may assume the tower has only one floor. There are many elements on the floor, such as monsters, herbs, keys and doors. There are at most 12 elements. A hero has H health points (Hp) at the beginning. If he walks into a place occupied by a monster, he may lose mi Hp according to the power of the monster. If his current Hp is no bigger than mi, he dies. Otherwise, the monster is killed and will not appear again. If he walks into a place occupied by a herb，he needs to eat it. His current Hp will be increased by hi according to the power of the herb, and the herb will not appear again. The hero’s Hp may be bigger than H. If he walks into a place occupied by a key, he can pick up the key. Each key has a color, and some keys may have the same color. One key can open only one door with the same color. If a key is picked up, it will not appear again. If he tries to walk into a place occupied by a door, he needs a key with the same color to open it. If he manages to open it, the door disappears, as well as the key. Now you are given the map of the floor and the description of the elements, you need to find the path leading the hero to the princess.

The input will consist of multiple cases. Your program should process to the end of the input file. In the first line of each case, there are three integers N, M, and H. The hero has H Hp at the beginning of the game. 3 ≤ N, M ≤ 12. H > 0. The next N lines describe the maze of the game, M characters each line. The characters is from the set {‘.’,’#’,’@’,’*’,’A’-‘Z’}.No other characters will appear.

• The character‘.’ represents an empty place. The hero can freely walk into these places.
• The character‘#’ represents some obstacles, such as walls, trees, etc. The hero can not walk into any obstacles.
• The character‘@’ represents the starting place of the hero. It is of course an empty place.
• The character‘*’ represents the place of the princess. If the hero manages to arrive at this place, he wins.
• The uppercase character ‘A’-‘Z’ represent the elements described before. There are totally T elements. 0 ≤ T ≤ 12. The elements are represented by distinct characters，which are the first T characters in the alphabet.

Following T lines are the description of the elements, one element per line. The first character is the same with the one in the maze. The second is a string describing the type of the element.

• If it is “Monster”, it is followed by an integer mi describing the hp the hero may lose if he meets with the monster.
• If it is “Herb”, it is followed by an integer hi describing the hp the hero may increase if he picks up the herb.
• If it is “Key”, it is followed by a word describing the color of the key.
• If it is “Door”, it is followed by a word describing the color of the door.

The output will consists of three lines for each case. The first line is in the format of “Case X:”. X is the number of the input case counting from 1. The second line is an integer describing the minimum number of steps to reach the princess. The hero can only move to the adjacent four places, and can never move out of the maze. You may assume there are walls around the maze. If there is no way to reach the princess, just output “Impossible!” The third line should be the path leading the hero to the princess. Each character of the path should be in the set of { “ ^ ” , ” < ” , ” v ” , ” > ” }, which means walking up, left, down and right. If there are many solutions, you should output in accordance with the following order: “ ^ ” , ” < ” , ” v ” , ” > ” . If the path does not exist, just output “Game Over!” Separate cases by one blank line.

5 5 5
.....
.###.
.#...
.#.##
@#..*

5 5 5
.....
.###.
.#...
.#.##
@#.#*

5 5 5
.....
.###.
.#...
.#A#D
@#BC*
A Monster 4
B Herb 5
C Monster 10
D Monster 5

5 5 5
*#B..
A.##.
...#.
.#.#.
@#...
A Door Red
B Key Red

Case 1:
16
^^^^>>>>vv<<vv>>

Case 2:
Impossible!
Game Over!

Case 3:
20
^^^^>>>>vv<<vv^^>>vv

Case 4:
28
^^>>vv>>^^^^<<>>vvvv<<^^<^<^