Ridges and Valleys
Memory limit: 32 MB
Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity.
Therefore, in order to plan the journey and know how long it will last, he must know the number of ridges
and valleys in the area he is going to visit. And you are to help Byteasar.
Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape of
a
square. For each field
belonging to the square
(for
), its height
is given.
We say two fields are adjacent if they have a common side or a common vertex (i.e. the field
is adjacent to the fields
,
,
,
,
,
,
,
, provided that these fields are on the map).
We say a set of fields
forms a ridge (valley) if:
- all the fields in
have the same height,
- the set
forms a connected part of the map (i.e. from any field in 
it is possible to reach any other
field in 
while moving only between adjacent fields and without leaving the set 
),
- if
and the field 
is adjacent to 
, then 
(for a ridge) or 
(for a valley).
In particular, if all the fields on the map have the same height, they form both a ridge and a valley.
Your task is to determine the number of ridges and valleys for the landscape described by the map.
