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.