Задачи
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.
Входные данные #1
6 100100 001010 000000 110000 111000 010100 8 01100101 01000001 00011000 00000010 11000011 10100010 10000001 01100000
Выходные данные #1
Case #1: 3 Case #2: 6