SCUSA Region ACM Balloon Logo ICPC Masthead
2007 South Central USA Regional Programming Contest

Another Version of the Truth

Introduction:

Influence is a board game; while it can be played on almost any layout, an interesting layout is a hexagonal NxN grid, such that the layout resembles a rhombus.

An example 9x9 board is as follows:

1 2 3 4 5 6 7 8 9
 \ \ \ \ \ \ \ \ \                
  * * * * * * * * * — A
   * * * * * * * * * — B
    * * * * * * * * * — C
     * * * * * * * * * — D
      * * * * * * * * * — E
       * * * * * * * * * — F
        * * * * * * * * * — G
         * * * * * * * * * — H
          * * * * * * * * * — I
On the above grid, F5 is adjacent to F4, F6, E5, E6, G4, and G5. (These coordinates are not used in the problem, but are useful for understanding the underlying adjacencies.)

The rules of Influence are simple; the pertinent details are as follows:

In the sample input below, the first player (represented by "!" marks) has only two Influence, that provided by the locations that his Manipulators are on; the second player (represented by "@" signs) has ten Influence, and the third player (represented by "#" marks) has four Influence. There are nine locations that provide Influence to no player, as they are equally distant from two or more of the players.

Given a particular board layout, answer this question: what would the resulting Influence be for each player's optimal move if they were making the last move in the game?

Moves are to be considered independently; that is, the maximum score for the second player should be calculated based on the original board layout, not the one after the first player's best move.

Input:

Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of the following components:

Output:

For each data set in the input, output the heading "DATA SET #K" where K is 1 for the first data set, 2 for the second, etc. Then print P lines, each representing the maximum score possible for, in order, the first, second, third (if playing), and fourth (if playing) player if they were to make a single last move.

Sample Input:

1
3
5
! . . # .
 . @ . . !
  . . . . #
   . . @ . .
    . . . . .

Sample Output:

DATA SET #1
5
13
7