English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Grzbiety i doliny (grz)
Grzbiety i doliny
Limit pamięci: 32 MB
Bajtazar lubi wędrować po górach. Podczas swoich wędrówek odwiedza wszystkie okoliczne grzbiety i doliny. Dlatego, aby dobrze zaplanować czas, musi wiedzieć, ile grzbietów oraz dolin znajduje się na obszarze, po którym będzie wędrował. Twoim zadaniem jest pomóc Bajtazarowi.
Bajtazar dostarczył Ci mapę obszaru, który wybrał jako cel swojej
kolejnej wyprawy.
Mapa ma kształt kwadratu o wymiarach 
.
Dla każdego pola 
tego kwadratu
(dla 
) podana jest jego wysokość
.
Mówimy, że pola sąsiadują ze sobą, jeżeli mają wspólny bok lub
wierzchołek (tzn. pole 
sąsiaduje z polami
, o ile pola o takich
współrzędnych mieszczą się na mapie).
Mówimy, że zbiór pól 
tworzy grzbiet (dolinę), jeżeli:
-
wszystkie pola z
mają tę samą wysokość,
-
zbiór
stanowi spójny kawałek mapy (z każdego pola ze
zbioru 
można przejść do każdego innego pola z 
,
przechodząc tylko z sąsiedniego pola na sąsiednie i nie
wychodząc poza zbiór 
),
-
jeśli
oraz pole 
sąsiaduje z 
, to
(dla grzbietu) lub 
(dla
doliny).
Twoim zadaniem jest wyznaczyć liczbę grzbietów oraz dolin dla krajobrazu opisanego przez otrzymaną mapę.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis mapy,
- obliczy liczbę grzbietów i dolin dla krajobrazu opisanego przez tę mapę,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna
liczba całkowita 
(
) oznaczająca rozmiar
mapy.
W każdym z kolejnych 
wierszy znajduje się opis kolejnego
wiersza mapy.
W 
-szym wierszu (dla 
) znajduje się
liczb całkowitych
(
),
pooddzielanych pojedynczymiodstępami.
Są to wysokości kolejnych pól w 
-tym wierszu mapy.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać dwie liczby całkowite oddzielone pojedynczym odstępem - liczbę grzbietów, a następnie liczbę dolin dla krajobrazu opisanego przez mapę.
Przykład
Dla danych wejściowych:
5 8 8 8 7 7 7 7 8 8 7 7 7 7 7 7 7 8 8 7 8 7 8 8 8 8
poprawną odpowiedzią jest:
2 1
natomiast dla danych:
5 5 7 8 3 1 5 5 7 6 6 6 6 6 2 8 5 7 2 5 8 7 1 0 1 7
poprawnym wynikiem jest:
3 3
Na powyższych rysunkach zaznaczone są grzbiety (linia ciągła) i doliny (linia przerywana).
Autor zadania: Zbigniew Czech.