Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3478
Binary Land

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Binary Land is a very simple action title for the Famicom with an interesting twist. You control, not one, but two penguins, Gurin (male) and Malon (female), who are in love with each other. While you are in direct control of one penguin, you indirectly control the other penguin, who moves in a mirror image fashion from the original penguin. When you move your penguin left, the other moves right, and vice versa. The goal of the game is to move both penguins from their own origins to the unique caged heart at the same time.

At the beginning of each stage, you can choose which penguin to control directly. There are many walls which stop penguins from moving into them. If a penguin trys to do so, it will remain in the original grid. Besides the caged heart and walls, spider webs are strewn about in the 10×15 maze. If one of the penguins hits the web, it will become stuck in place until the other penguin moves to its neighbour and helps the stuck penguin move from the spider web to its grid. This process costs 11 seconds. Generally, it costs 5 seconds to move both penguins simultaneously. But when one of the penguins is stuck, moving the penguin which you directly control takes 2 seconds, while moving the other penguin takes 3 seconds.

What's the earliest time that Gurin and Malon can meet at the caged heart?

Binary Land Sample 1 Sample 2
Sample 3 Sample 4 Sample 5

Input

There are multiple test cases. The first line of input is an integer T ≈ 100 indicating the number of test cases.

Each test case contains 13 lines. The first 10 lines are the 10×15 maze, the 11th line is the origin of Gurin, the 12th line is the origin of Malon, and the 13th line is always a blank line. The maze is made up of unique caged heart ('H'), spider webs ('O'), walls ('X'), and empty grids ('.'). The origins of penguins cannot be walls.

Output

For each test case, output the earliest time, or -1 when it's impossible.

Sample Input

5
.......H.......
.XXX.XXX.XXX.XX
XX.X.X.XXX.X.X.
..O....X.......
.XXXXX.X.XXXXX.
.......X....O..
XX.X.X.X.X.X.XX
.......X.......
.XXXXXXXXXXXXX.
.......X.......
1 15
1 1

.......H.......
.X.X.XXXXX.X.X.
.X.X.X.X.XXXXX.
...X..OX...X...
.XXX.XXXXX.X.XX
.......X.......
XX.XXX.X.XXXXX.
O..X...X.......
.X.X.X.XXX.X.XX
.....X.X.......
10 9
10 7

...XO..H.......
OX.X.X.X.X.X.XX
OXOX.XOX.X.X.X.
OX...X.XO..X..O
.XXXXXXX.XXX.XX
.O.XO..X..O....
.X.X.X.XXX.XXX.
OX.X.XOXO..X.O.
.XOX.X.X.X.X.X.
.X...X.X.....X.
10 9
10 7

.......H.....X.
.XXX.XXXXX.X.X.
XX.X.X.X.X.X.X.
.......XO..X...
.XXXXX.XXX.XXX.
.......X.X.....
.X.X.XXX.XXX.XX
.......X...X..O
XXXXXX.X.X.X.X.
.......X.X.....
1 10
1 4

.......H.......
.X.X.X.X.X.X.X.
.X.X.X.X.X.X.X.
.......X.......
.X.X.X.X.X.X.X.
.......X.......
.X.X.X.X.X.X.X.
.......X.......
.X.X.X.X.X.X.X.
......OX.......
10 1
10 7

Sample Output

35
140
-1
40
99

References


Author: WU, Zejun
Contest: The 11th Zhejiang University Programming Contest
Submit    Status