Sane's Monthly Algorithms Challenge: October 2008

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\times N\times 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 laborious 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.

Input Specification

The first line of input contains a single integer, $N$ $(1\le N\le 10)$, representing the size of the cube.

The next line is blank.

$N$ groups, each representing one level, occur in the following format:

$N$ lines of $N$ characters, each Soil (.) Rock (X) or Gold (*), followed by a blank line.

The levels are listed, in order, from ground-level to the deepest level.

Output Specification

On a single line, an integer representing the amount of gold you can retrieve. If no gold can be dug, then output $0$.

Sample Input

4

.X..
.X..
.XXX
.XXX

.X..
....
.X.X
.X..

XX..
X...
..XX
.X.*

*X*.
X...
....
*X..

Sample Output

3

Explanation

The following route is taken to get $3$ pieces of gold. Diagrams and an explanation are on the next page.

.X..
1X..
.XXX
.XXX

.X..
234.
.X5X
.X67

XX..
X...
..XX
.X.8

*XDC
XFEB
HG.A
IX.9

In one dig we can retrieve $3$ of the $4$ pieces of gold. The $4$th 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.