eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Rain Forest Canopy

Rain Forest Canopy

Ліміт часу 10 секунд
Ліміт використання пам'яті 64 MiB

A tropical rainforest is typically divided into four main layers: the emergent, canopy, understory, and forest floor layers. Of the four, it is quite tricky to distinguish the emergent layer from the canopy layer. The emergent layer contains a small number of very large trees, which grow above the general canopy, reaching heights of 45 to 55 metres. The canopy layer is the richest layer of the diverse rainforest, and ranges in heights of 30 to 45 metres tall. Because of bio- diversity crisis, monitoring rainforest canopy is the mission of Whole Forest Observatory, which is trying to identify suitable canopy research sites.

A group of engineers have found a simple satellite imagery technique that can mark canopy layers on a spot image of a wide rainforest area. The spot image is a square and is stored as pixels, i.e., small cells containing either a 1 or a0. Each pixel carries some information about a particular 1 km^2 region. A pixel location contains a 1 if part or its entire represented region is a canopy layer and a 0 if otherwise.

The following assumptions hold:

  • A canopy layer is represented by at least a single 1.

  • Cells with adjacent sides on a common pixel that contains a 1, comprise the canopy layer. A single large canopy layer image will contain all 1’s.

  • Distinct canopy layers do not touch one another.

  • There is no wrap-around, i.e., the pixels on the bottom are not adjacent to the top, and the left is not adjacent to the right.

Write a program that reads spot images and correctly counts the number of canopy layers in these images.

Вхідні дані

The input consists of up to 1000 test cases. Each test case describes a spot image of a rainforest area, which starts on a new line with a positive integer N, (1N40) indicating the dimension of the image. The next N lines of each test case delineate the pixelated representation of the image.

Вихідні дані

For each test case, produce a single line of output that starts with the prefix "Case #x: " where x represents the case number (starting from one and incrementing at each new test case), followed by a single space, and then the result, i.e., the number of canopy layers in the spot image.

Приклад

Вхідні дані #1
6
100100
001010
000000
110000
111000
010100
8
01100101
01000001
00011000
00000010
11000011
10100010
10000001
01100000
Вихідні дані #1
Case #1: 3
Case #2: 6
Джерело ACM-ICPC Malaysia al-Khawārizmī National Programming Contest 2013 (al-Khawārizmī' 2013), 21-22 September 2013