In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.