2005 South Central USA Regional Programming Contest
Intl Prog Contest
South Central US Regional
Janken, also known by the name rock paper scissors, is a popular Japanese childrens' game. In the grand tradition of game development, one company has decided to put a strategic twist on a classic title. The resulting war "simulation," Janken Tactics, is in development as we speak. You have been hired onto the team as a programmer, and put to work on the move validation code.
Janken Tactics takes place on a map represented by a hex-hex grid with five cells on each side. Each cell on the grid has a certain terrain type, which helps or hinders movement through the cell. Normally, moving into an adjacent cell costs one movement point, but the terrain on that cell may cause it to cost more:
4 5 6 7 8 9 3 \ \ \ \ \ \ 2 \ \ * * * * * -- A 1 \ \ * * * * * * -- B \ \ * * * * * * * -- C \ * * * * * * * * -- D * * * * * * * * * -- E * * * * * * * * -- F * * * * * * * -- G * * * * * * -- H * * * * * -- Iwith letters coming first in the coordinate system. The center cell of the top row is A7, the rightmost point of the grid is E9, and so on. On the hex grid above, adjacent cells are those to the immediate left and right and those immediately along the diagonals. For example, the cells adjacent to E5 are D5, D6, E4, E6, F4, and F5.
As one might expect of a game based on Janken, there are three unit types: the Guardian (rock), the Mage (paper), and the Swordsman (scissors). Units also have 10 movement points that they can expend per move. And, as in Janken, the units each have their strengths and weaknesses:
Your goal is to determine whether a given unit can execute a certain move, and if so how many movement points are left over after the move. The code should maximize the number of movement points left at the end of the move, so that the unit has more choices during any potential combat that may occur. Invalid moves may occur if:
Input to this problem will begin with a line containing a single integer n indicating the number of data sets. For each data set, the next six lines are a representation of the hex-hex grid's terrain, with F representing fields, W representing woods, H representing hills, M representing mountains, and U representing underwater cells.
The next line of each data set will consist of two integers M P (1 <= M, P <= 10) representing the number of units on each side of the battle. Following that are M lines with two values T L, where T is the type of unit (G for Guardian, M for Mage, S for Swordsman) and L is the starting location for that unit represented as described above. The P lines following that are a similar representation for the second side.
The next line of each data set consists of an integer V (1 <= V <= 100) representing the number of moves to test. The next V lines contain two values S E, where S and E are coordinates in the proper format describing the starting cell (and therefore unit) and attempted ending cell for that move. Note that moves may involve either of the sides.
For each data set, first print "Game #X" where X is the number of the data set, starting with 1. For each move in each data set, print "Move #N (S -> E): Successful (M points left)" if the move was successful, or "Move #N (S -> E): Unsuccessful" if the move was unsuccessful. N is the move number, starting at 1; S is the starting coordinate and E the destination coordinate, in the representation described above; M is the number of movement points left at the end of the move.
1 U U U W W U F F F F W W F H H H F W W F H F F H F W W F H F F F F F W W F H F F H H H W F H M M M M W F F F F F W W W W W 3 3 G E5 M D5 S F4 G F8 M A8 S C4 2 E5 E9 D5 F8
Game #1 Move #1 (E5 -> E9): Successful (5 points left) Move #2 (D5 -> F8): Unsuccessful