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

Rain Forest Canopy

Rain Forest Canopy

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 \textbf{45} to \textbf{55} metres. The canopy layer is the richest layer of the diverse rainforest, and ranges in heights of \textbf{30} to \textbf{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 \textbf{1} or a\textbf{0}. Each pixel carries some information about a particular \textbf{1} km^2 region. A pixel location contains a \textbf{1} if part or its entire represented region is a canopy layer and a \textbf{0} if otherwise. The following assumptions hold: \begin{itemize} \item A canopy layer is represented by at least a single \textbf{1}. \item Cells with adjacent sides on a common pixel that contains a \textbf{1}, comprise the canopy layer. A single large canopy layer image will contain all \textbf{1}’s. \item Distinct canopy layers do not touch one another. \item 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. \end{itemize} Write a program that reads spot images and correctly counts the number of canopy layers in these images. \InputFile The input consists of up to \textbf{1000} test cases. Each test case describes a spot image of a rainforest area, which starts on a new line with a positive integer \textbf{N}, (\textbf{1} ≤ \textbf{N} ≤ \textbf{40}) indicating the dimension of the image. The next \textbf{N} lines of each test case delineate the pixelated representation of the image. \OutputFile For each test case, produce a single line of output that starts with the prefix "\textbf{Case #x: }" where \textbf{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.
Лимит времени 10 секунд
Лимит использования памяти 64 MiB
Входные данные #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