Shark |
The photos are transmitted by
radio to the central computer of the beach guardians association,
where they are analyzed. The main goal of such processing is to
detect sharks, in order to issue an immediate shark alarm to the
corresponding beach, if that is the case.
Processing is rather
sophisticated, since not all sea animals are sharks: there are
small fish (sardines), slightly larger fish (mackerel, salmons),
large fish (groupers), sea mammals (dolphins, whales), reptiles
(turtles). When seen from afar (from the satellite, that is),
dolphins are similar to sharks, but the system must distinguish
them or we risk raising false alarms just because a group of
easygoing dolphins has approached the beach to play with the
tourists.
Satellite photographs are digitally preprocessed and are
now represented by a grid. In each square in the grid there is
either a lower case letter (from `a' to `z') or there is nothing,
i.e., the square is empty. Each sea animal is represented by a set
of adjacent squares in the grid all bearing the same letter. Two
grid squares are adjacent if they have one side in common.
All animals have a distinct rectangular shape, except sharks, as
explained below. Single square animals (i.e., animals which fill
one square only) are sardines. Two square animals (filling a 1 by
2 rectangle) are mackerels; longer animals with width 1 are
salmons. Square animals larger than sardines are turtles (there
can be 2 by 2, 3 by 3, etc., turtles). Groupers are rectangular
with width 2 and length greater than 2. Dolphins are rectangular
with width 3 and length greater than 3. Whales are rectangular
with width 4 and length greater than 4. Finally sharks are similar
to dolphins, having width 3, but their shape is not a rectangle.
As a matter of fact, the tail fin for dolphins is horizontal and
that is what gives dolphins a digitalized rectangular shape.
Sharks, on the other hand, have a vertical tail fin, which is
recognized by an extra square along the middle row of squares that
represent the body of the shark.
All other shapes will have been
erased during preprocessing, which guarantees that no unknown
species can occur in the digitalized representation. As an
example, consider the following photograph, where we can observe
all the mentioned species.
b | c | f | g | h | |||||||
b | a | a | b | c | a | j | k | y | y | y | |
b | c | a | k | y | y | y | |||||
c | a | y | y | y | |||||||
z | z | z | z | z | z | u | u | u | |||
z | z | z | z | z | z | s | u | u | u | ||
z | z | z | z | z | z | s | s | s | u | u | u |
t | t | t | t | s | s | s | u | u | u | ||
t | t | t | t | t | s | s | s | u | u | u | |
t | t | t | t | s | s | s | u | ||||
h | h | ||||||||||
b | b | b | b | f | f | f | h | h | |||
b | b | b | b | f | f | f | h | h | |||
b | b | b | b | g | g | g | g | h | h | ||
b | b | b | b | g | g | g | g | p | p | p | |
b | b | b | b | g | g | g | g | p | p | p |
On the upper left corner we see 3 mackerels. More to the right there are 2 salmons (one bigger than the other). Still more to the right, 6 beautiful sardines swim merrily. On the upper right corner, a giant turtle watches a ferocious shark, just below. There are 2 other smaller sharks and a large dolphin in the center rows. On the lower left corner a whale peacefully sits next to a second dolphin. On the lower right corner, 3 groupers wonder what they are doing in this crowded part of the ocean.
Your task is to write a program
that processes a digitalized representation of a sea photograph in
the format explained above and outputs the number of sardines, the
number of mackerels, the number of salmons, the number of
groupers, the number of turtles, the number of dolphins, the
number of whales and the number of sharks present.
The first line of input contains two numbers, L and C, representing
the number of lines and the number of columns in
the grid, respectively. Each of the remaining L lines contains
exactly C characters, which are either lowercase letters or
points. These lines represent the grid. A letter means that an
animal or a part of an animal occupies the corresponding
square. Points indicate that the corresponding square is empty.
The maximum number of lines and number of columns for the grid is 64.
The output is just one line with 8 numbers: the number of sardines,
the number of mackerels, the number of salmons,
the number of groupers, the number of turtles, the number of dolphins,
the number of whales and the number of sharks,
as counted in the input. There is a single space between consecutive
numbers and nothing else on the line (other than
the end of line marker).
1 16 12 b...c.fgh... baabca.jkyyy ...bcak..yyy ....ca...yyy zzzzzz...uuu zzzzzz.s.uuu zzzzzzsssuuu .tttt.sssuuu ttttt.sssuuu .tttt.sss.u. .........hh. bbbb..fffhh. bbbb..fffhh. bbbbgggg.hh. bbbbgggg.ppp bbbbgggg.ppp
6 3 2 3 1 2 1 3