405071: GYM101775 E Snakebird

Do you like puzzles, fruits and the notion of crossing a snake with a bird for no good reason? If the answer to at least one of those questions is yes, then Snakebird might be the game for you. Solve your way through this head-scratcher of a puzzle game and help the snakebirds sate their hunger.

The game starts with a board of M × N cells, at the beginning each cell is one of the following types.

• 'R', 'G', 'B': Your snakebirds' head. You'll have at least 1 snakebird and at most 3 snakebirds on the board. Once you are moving a snakebird, other snakebirds are treat as obstacles. That means you can not enter a cell that is occupied by other snakebirds.
• '>', '<', '^', 'v': Your snakebirds' body is pointing to another body that is closer to the head. These 4 types are pointing right, left, up, down respective. It's guaranteed that each head/body is pointed by exactly one other body except the last one. It's also guaranteed that each body is pointing to a head/body.
• '.': Empty cell. Your snakebirds can enter empty cells. When a snakebird enters an empty cell, it's head goes into this cell and all it's other bodies go into the position of previous head/body. This action finishes instantly.
• '#': Obstacle. Your snakebirds can not enter obstacles, but if any piece of the snakebird is one cell above the obstacle, the obstacle supports the snakebird and the snakebird will stop falling.
• '|': Spike. Your snakebirds can either enter spikes or falling into the spikes. However, if this happened, the snakebird dies.
• '@': Fruit. Your snakebirds can enter the cell of fruit. When a snakebird enters a cell of fruit, the fruit disappears and the cell becomes an empty cell. Meanwhile, all head/body of the snakebird stay at the position and the snakebird has a new head in the cell of the fruit. The previous head becomes a body connecting with the new head. But when snakebird is falling the fruit is treated as an obstacle even the head of any snakebirds falling towards the fruit.
• 'X': Exit. There is exactly 1 exit on the board. Before all the fruits disappear, the exit is inactive and just like an empty cell. After ALL the fruits disappear, anytime a snakebird's head is in the Exit cell, the snakebird disappears and goes into heaven. Even if the snakebird is falling. If a snakebird falls on a spike or falls out of the board while it's head falls into the Exit cell, it dead before going to heaven. :(

On each move, you can select one of the snakebirds, and move it's head to one of the adjacent cells(four directions) to enter an empty/fruit cell. After each move, something magic is happening, your snakebirds are subject to gravity, which means all snakebirds without support start falling until they land on some obstacles(or other snakebirds with support) or dead. Falling on spike or falling out of the board causes dead. The shape of the snakebird doesn't change during the falling.

It's guaranteed that nothing is going to fall at the beginning.

To help Redbird, Greenbird and Bluebird win the game, you need to send all snakebirds to heaven alive. Find out the minimal number of moves needed.

The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case contains 2 numbers M, N, the rows and columns of the board. The following M lines, each line contains N characters representing the board.

• 1 ≤ T ≤ 10.
• 1 ≤ N, M ≤ 20.
• The total number of fruits, snakebirds head/body on a board is at most 10.
• It's guaranteed that nothing is falling at the beginning.

For each test case, output one line containing "Case #x: y" in the one line. x is the test case number (starting from 1) and y is the minimum moves needed to send all snakebirds to heaven. If it's impossible to do that, output -1 instead.

8
4 4
....
...v
X..G
##.#
4 4
....
...v
X..G
#..#
4 4
..X.
....
.R.@
####
4 7
.......
.......
>>B|..X
#######
4 7
.......
v......
>>B|..X
#######
4 5
>R...
##...
##.X.
##...
4 5
>R...
##...
##|X.
##...
9 11
.......X...
...........
....#......
...........
.#.........
.#.........
.#..#...B<<
....#..G<<^
.......####

Case #1: 3
Case #2: -1
Case #3: 6
Case #4: -1
Case #5: 6
Case #6: 2
Case #7: -1
Case #8: 46

In the first test case, the green snakebird can go to left and enter the exit.

In the second test case, as the gap is too big, it's impossible to enter the exit.

In the third test case, the red snakebird needs to go right to eat the fruit, then enter the exit.

In the forth test case, there is a spike in the middle, the snakebird of length 3 is not able to cross through.

In the fifth test case, the snakebird of length 4 is able to cross through.

In the sixth test case, the snakebird can just go right twice and jump to the exit.

In the seventh test case, the snakebird can also jump to the exit, but a spike kills it at the same time it reaches the exit.

The last sample looks like the picture below.