[USACO 2011 Ope B]3D Space Exploration
题号:NC24690
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

Farmer John's cows have finally blasted off from earth and are now floating around space in their Moocraft. The cows want to reach their fiery kin on Io, a moon of Jupiter, but to do so they first must navigate the dangerous asteroid belt.
Bessie is piloting the craft and must guide it through this treacherous N x N x N (1 <= N <= 100) sector of space. All asteroids in this sector comprise some number of 1 x 1 x 1 blocks of space-rock connected along their faces (two blocks sharing only a vertex or only an edge count as two distinct asteroids).
Please help Bessie by counting the number of distinct asteroids in the field.
Consider a 3 x 3 x 3 space where the first slice of space looks like this, with 'M' indicating the starting location of the Moocraft (1,1,1) and 'D' is the destination at (3,3,3). In these maps, these markers serve mostly as map orientation rather than providing useful information to solve the problem.
In these diagrams and also in the input file, the *'s represent
asteroid chunks and each '.' represents a vast void of empty space.

   Close slice    Middle slice     Far Slice     Assembled with overlaps
     +---+            +---+          +---+                  +---+ Far
     |M..|            |..*|          |...|                  |...|
     |.*.|            |.*.|          |.*.|                +---+.|
     |...|            |*..|          |..D|                |..*|D|
     +---+            +---+          +---+              +---+.|-+
                                                        |M..|.|
                                                        |.*.|-+
                                                        |...|
                                                  Close +---+

Visual inspection shows three asteroids, including a long one through
the middle of the map. Here's a map with the asteroid pieces labelled:

                                  +---+ Far
                                 /|...|
                                / |.1.|
                               /  |...|
                              /   +---+
                             +---+   /
                            /|..3|  /  
                           / |.1.| /
                          /  |2..|/
                         /   +---+
                        +---+   /
                        |...|  /
                        |.1.| /
                        |...|/
                  Close +---+

输入描述:

* Line 1: A single integer: N
* Lines 2..+1: Line i-1 contains line 1 + ((k+1)%N) of slice int ( (i+N-1)/N ): N characters

输出描述:

* Line 1: A single integer indicating the number of asteroids in the field
示例1

输入

复制
3
...
.*.
...
..*
.*.
*..
...
.*.
...

输出

复制
3