Farmer John 的母牛终于从地球升空,如今乘着 Moocraft 在太空漂浮。她们想去木星卫星 Io 看望火热的亲戚,但首先必须穿过危险的小行星带。
Bessie 驾驶飞船,必须穿过这片危险的 $N \times N \times N$ 太空区域,$1 \le N \le 100$。这里每颗小行星由若干 $1 \times 1 \times 1$ 太空岩石块按面相连组成(只共享顶点或边的两个块算不同小行星)。
请帮助 Bessie 统计这片区域中不同小行星的数量。
考虑 $3 \times 3 \times 3$ 空间,其第一层如下,$M$ 表示 Moocraft 起点 $(1,1,1)$,D 是终点 $(3,3,3)$。这些标记主要用于说明地图方向,而不是提供解题的有效信息。
图和输入中,* 表示小行星块,. 表示广阔的空旷太空。
近层 中层 远层 重叠组装
+---+ +---+ +---+ +---+ 远
|M..| |..*| |...| |...|
|.*.| |.*.| |.*.| +---+.|
|...| |*..| |..D| |..*|D|
+---+ +---+ +---+ +---+.|-+
|M..|.|
|.*.|-+
|...|
近 +---+观察可见三颗小行星,其中一颗长条状贯穿地图中央。下面标出了各小行星的块:
+---+ 远
/|...|
/ |.1.|
/ |...|
/ +---+
+---+ /
/|..3| /
/ |.1.| /
/ |2..|/
/ +---+
+---+ /
|...| /
|.1.| /
|...|/
近 +---+输入格式
- 第 1 行:一个整数 $N$。
- 第 $2..N^2+1$ 行:第 $i-1$ 行包含第 $\operatorname{int}((i+N-1)/N)$ 层的第 $1 + ((k+1)\%N)$ 行,共 $N$ 个字符。
输出格式
- 第 1 行:一个整数,表示这片区域的小行星数量。
样例
输入格式 1
3 ... .*. ... ..* .*. *.. ... .*. ...
输出格式 1
3
题目作者:Andre Kessler,2010