Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3837
Miner

Time Limit: 5 Seconds      Memory Limit: 65536 KB

Bob is recently playing a game called Minecraft, especially a mod called Industrialcraft 2. The things you can do in this mod is to build machines. One of the basic machines is Miner.

The Automated Miner is the lazy man's answer to mining. Once you place the miner on the ground, then place a drill together with a scanner in the right position and provide enough electricity and mining pipes, the miner will automatically place mining pipes under it and mines all the ores in the scan range of the scanner.

Miner

However, Bob found that the miner's AI is limited, it follows the greedy strategy when mining, so there exists potential space for improvement to its electricity cost.

Mining is processed layer by layer. The range n*n is determined by the scanner you are using. It can be 5*5, 7*7 or 9*9. So the problem you are facing now is to design the best strategy which wastes the least electricity on useless stones.

A map of the current layer will be provided to you. It is of size n*n. A typical map of size 5*5 is shown below.

00111
00191
09vX1
09X2@
099@1

'v' shows the position of the drill, that block has already been mined. It is guaranteed 'v' is at the center of this square region, and there is only one 'v' in each map.
'0'-'9' in the map shows a stone which requires the digit amount of electricity. For example, '9' means there is a stone at that position which requires 9 units of electricity to be mined.
'@' shows a block with a precious ore.
'X' shows a block with an obstacle. Your drill is not powerful enough to mine this obstacle.

A block can be mined only after at least one of its adjacent blocks has already been mined. The block where the drill is in has already been mined. Two blocks are adjacent if they share an edge.

Your task is to tell the least units of electricity required to mine all the ores in a given map.

Note that, in Minecraft, ores are generated following specific rules. Generally, ore blocks appear together, they are generated as ore clusters.

*@*
@@@
*@*

The previous picture is a basic ore cluster, '*' can be any block.

*@@*
@@@@
*@@*

The previous picture shows two ore clusters stacking together.

Note that Uranium ore being extremely precious does not appear as ore clusters. They can appear in any shape. However, there will not be more than 3 Uranium ores in a single map.

Input

There are multiple cases. The first line contains one integer T which is the number of test cases.
For each case, the first line contains an integer n( 5 ≤ n ≤ 9, n is an odd number).
For the next n lines, each line contains n characters showing the map. Note that, the map will contain only complete ore clusters. There will not be more than 3 Uranium ores on the map.

Output

One integer for each test case indicating the least units of electricity required to mine all ores. In case, it is impossible to mine all the ores, just output -1 instead.

Sample Input

3
5
11111
X1111
XXv11
@X111
1X111
5
@100@
32@00
0@v@0
00@00
0000@
7
0@00000
@@@0000
0@03000
002v100
0005000
0000000
0000000

Sample Output

-1
1
1

Hint

Sample 1: The ores are blocked by obstacles, you cannot mine all of them.
Sample 2: Mine the stone with '1', then you can get all the ores. Note that this sample is valid because there is a complete ore cluster in the middle and three Uranium ores. The middle ore has already been mined by the drill. Sample 3: Mine the stone with '1', then you can get all the ores.


Author: GONG, Yuan
Source: ZOJ Monthly, November 2014
Submit    Status