401851: GYM100541 J Math Magic

A Math Magic game consists of a number of equal-sized blocks. Each block in Math Magic is divided into 4 triangles where each triangle takes a color from Blue (B), Green (G), Red (R), or Yellow (Y) and an integer from 0 to 9.

Starting with the center block, at each step a player can adjoin a new block in one of four directions along the horizontal or vertical axes centered at the center block. The new block is attached to an existing block in such a way that the two corresponding adjoined triangles must have the same color. The score of each block is calculated based on the color of the adjoined triangle, the integer in the adjoined triangle of the new block and the sum of four integers in the new block as follows:

If a block cannot be added in the board or the player does not wish to include in the board, then its score is –S and the block is skipped. Notice that the center block, i.e. the first block, does not have a score. For example, consider the following steps to add a new block and their corresponding scores

S = 4 + 4 + 0 + 1 = 9

x = 4

Color of the adjoined triangle: red

Score = S * x = 9 * 4 = 36

S = 1 + 3 = 4

x = 3

Color of the adjoined triangle: yellow

Score = 4

Given a list of blocks, a player will use the first one as the center block and either add or skip the remaining blocks to the board one at a time in sequence. The blocks can be rotated before being added to the board but they must be considered in the same order as given. Your task is to find the maximum total score a player could get.

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 40. The following lines describe the datasets.

The first line of each dataset contains an integer n(n≤250, 000), which is the total number of blocks including the center block as the first one. For the next n lines, each line contains 8 characters representing the colors and integers for the block’s triangle in clockwise order: c₁n₁c₂n₂c₃n₃c₄n₄ where c_i (c_i takes values from Y, R, G, or B standing for yellow, red, green or blue respectively), n_i (n_i takes an integer value from 0 to 9) is the color and integer of the i triangle respectively (1 ≤ i ≤ 4).

For each dataset, write on one line the maximum point score a player could get.

1
10
G3B7B3Y6
R9B2B0G3
G0Y2Y1R7
G2B2B7G9
G2B9Y3G1
R9B1R4Y8
G5G3Y1R6
G2R6R5B4
R6R6R3B4
R2B4Y4G3

517