소행성 지대 우주탐사

실행 시간 제한	메모리 제한
1 초	128 MB

📃 해결할 문제

'가디언즈 오브 갤럭시'의 슈퍼 히어로 팀은 우주선을 타고 우주 공간을 떠돌고 있습니다. 그들은 해골 모양의 행성인 노웨어로 가려고 하지만, 그렇게 하려면 먼저 위험한 소행성 지대를 통과해야 합니다.

로켓이 이 우주선을 조종하고 있고, 그는 이 위험한 N x N x N (1 <= N <= 100) 섹터의 우주 공간을 통과해야 합니다. 이 섹터의 모든 소행성들은 일부 1 x 1 x 1의 우주 바위 블록들로 구성되어 있고, 그들의 면들은 연결되어 있다(오직 꼭지점이나 오직 가장자리만을 공유하는 두 블록은 두 개의 별개의 소행성으로 취급한다).

로켓에게 도움을 주고, 필드의 소행성 수를 셈으로써, 필드를 탐색하는 것을 도와주세요.

예를 들어 아래와 같은 3 x 3 x 3의 공간을 생각해봅시다.

'M'은 우주선의 시작 위치(1,1,1)를, 'D'는 (3,3,3)의 목적지를 나타냅니다.

아래 지도에서 'M'과 'D'는 문제를 해결하는데 유용한 정보를 제공하기보다는주로 지도의 방향을 나타나는 데 사용됩니다.

이 다이어그램들과 입력 파일에서, '*'는 소행성 덩어리들을 나타내며, '.'는 빈 공간을 나타냅니다.

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

육안으로 보면 지도의 중앙을 가로지르는 긴 소행성을 포함한 총 3개의 소행성을 보여줍니다. 아래는 소행성 조각에 번호가 매겨진 지도입니다:

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

💻 입력

첫 번째 줄 : 한 개의 정수: N
두 번째 줄부터 N^2+1번째 줄: i-1 번째 줄은 슬라이스 int ((i+N-1)/N )의 1 + ((k+1)%N) 줄에 속함: N개의 문자들

🖨️ 출력

첫 번째 줄 : 필드 안의 소행성 개수를 나타내는 한 개의 정수

💻 예제 입력 1

3
...
.*.
...
..*
.*.
*..
...
.*.
...

🖨️ 예제 출력 1

출처: USACO 2011 US Open Bronze 3