ZOJ Problem Set - 3837
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.
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.
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.
There are multiple cases. The first line contains one integer T which is the number of test cases.
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.
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
-1 1 1
Sample 1: The ores are blocked by obstacles, you cannot mine all of them.
Author: GONG, Yuan
Source: ZOJ Monthly, November 2014