4492: D. Sternhalma
内存限制：512 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：0
通过：0
题目描述
Pico the Puppy, together with FuuFuu and Kotsuki, lives in the KFP apartment. They often play a board game together called Sternhalma, commonly known as Chinese checkers. The objective of the game is to race all of one's pieces across the hexagram-shaped board to the opposite side, using single-step moves or moves that jump over other pieces.
One day, Pico wants to play Sternhalma again, but Kotsuki is out at work, and FuuFuu is still sleeping. Feeling bored, Pico intends to play on his own for a while. Pico simplifies the board into the shape shown in the picture below, with a total of 19 grids, and he assigns a score to each grid.
Initially, he places a number of pieces on the board. Then, he moves the pieces according to the rule set by himself, selecting either of the following two types of moves for each turn:
- Remove any piece directly from the board, getting no scores.
- Remove a piece by jumping over it. Formally, for two adjacent pieces A and B, if the symmetric position of A with respect to B is not out of bounds and no piece is placed there, then A can jump over B, and B is removed from the board. The total score will be increased by the score assigned to the grid where B is located before being removed. (We consider two pieces adjacent if and only if the grids where the two pieces are located share an edge.)
The initial score is 0. Pico will keep removing the pieces until there are no pieces left on the board. For different initial placements of pieces, he wants to know the maximum score he can get.
输入格式
The first five lines contain 19 integers, indicating the scores assigned to the grids. The first line contains 3 integers indicating the first row of the board, the second line contains 4 integers indicating the second row of the board, and so on. Each score ranges between -106 and 106.
The next line contains an integer n (1 ≤ n ≤ 104), indicating the number of initial placements of pieces.
Each of the n initial placements occupies five lines. Each line contains a string consisting of only . or #. The first line contains 3 characters indicating the first row of the board, the second line contains 4 characters indicating the second row of the board, and so on. # denotes that there is a piece at this position, while . denotes that there is none.
The next line contains an integer n (1 ≤ n ≤ 104), indicating the number of initial placements of pieces.
Each of the n initial placements occupies five lines. Each line contains a string consisting of only . or #. The first line contains 3 characters indicating the first row of the board, the second line contains 4 characters indicating the second row of the board, and so on. # denotes that there is a piece at this position, while . denotes that there is none.
输出格式
For each initial placement of pieces, output the maximum score in a single line.
输入样例 复制
9 2 2
3 3 7 2
0 3 6 8 5
4 7 7 5
8 0 7
3
...
..#.
..##.
....
...
...
....
.##..
..#.
...
###
####
#####
####
###
输出样例 复制
8
14
105
数据范围与提示
The first initial placement of the sample is shown in the picture below. Obviously, only one piece can be removed by jumping over it.
For the second initial placement of the sample, the moves to obtain the maximum score are shown in the following picture.