QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

#21229. 三維太空探索

Statistics

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.