W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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:
Twoim zadaniem jest wyznaczyć liczbę grzbietów oraz dolin dla krajobrazu opisanego przez otrzymaną mapę.
Napisz program, który:
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.
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ę.
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.