编程介的小学生 2017-08-28 09:32 采纳率: 20.3%
浏览 870
已采纳

Miner

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

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-09-12 15:53
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 基于单片机AT89C51下的交通信号灯设计
  • ¥15 数电设计题 没有设计思路 不知道用什么芯片进行设计 求提供设计思路
  • ¥15 在动态多目标优化问题中,第一幅图展示的是问题DF6的相关定义和绘制的POS和POF图,请问图中公式PS(t)和PF(t)是如何推导的
  • ¥60 设计一种优化算法结合案例给出智能仓储四向穿梭车的调度计划
  • ¥15 Errno2:No such file or directory,在当前文件确实没有该图片,怎么解决?
  • ¥15 博世摄像头数据存储的问题(iscsi)
  • ¥15 如何实现对学生籍贯信息管理系统的选择排序
  • ¥15 写一个51单片机的时钟代码
  • ¥15 git clone报错
  • ¥15 3d-slicer超声造影动态图像导入报错