Sane's Monthly Algorithms Challenge: October 2008
Digging for Gold (Junior Level)
Some ground has been selected for you to search for gold. Core samples
and metal detectors have created an accurate picture of what the
underground environment looks like.
The data has been simplified to an n x n x n cubic grid of soil, rock, and gold. Soil can be dug. Rock is impossible to dig through. Gold can be obtained by digging to it.
Digging for gold can be a long and labourious process. Fortunately for you, a software-driven digging rig is making the task programmable via remote control.
With your special digging rig, you may dig from your current location to any adjacent location. However, you can not dig upwards. You start at ground-level, and you may never dig off the cube. At any time you may bring your rig back up to ground-level and repeat this process. Your task is to remotely gather as much gold as possible.
InputThe first line of input contains a single integer, n (1 ≤ n ≤ 10), representing the size of the cube.
The next line is blank.
ngroups, each representing one level, occur in the following format:
ncharacters, each Soil (
.) Rock (
X) or Gold (
*), followed by a blank line.
The levels are listed, in order, from ground-level to the deepest level.
OutputOn a single line, an integer representing the amount of gold you can retrieve. If no gold can be dug, then output 0.
ExplanationThe following route is taken to get 3 pieces of gold. Diagrams and an explanation are on the next page.
.X..In one dig we can retrieve 3 of the 4 pieces of gold. The 4th piece can never be retrieved since it is surrounded by rock.
Below is the data's corresponding diagram. It is shown in 4 slices (whereas the test data is listed in 4 levels), which combine to form the cube.
White is soil.
Grey is rock.
Orange is untouched gold.
Purple is retrieved gold.
Green is the path taken.
The number inside each green cube indicates the order of visitation.
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 03, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3