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