Powódź
Limit pamięci: 128 MB
Bajtogród, stolica Bajtocji, to malownicze miasto położone w górskiej
kotlinie. Niestety ostatnie ulewne deszcze spowodowały powódź - cały
Bajtogród znalazł się pod wodą. Król Bajtocji, Bajtazar, zebrał swoich
doradców, w tym i Ciebie, aby radzić jak ratować Bajtogród. Postanowiono
sprowadzić pewną liczbę pomp, rozmieścić je na zalanym terenie i za ich
pomocą osuszyć Bajtogród. Bajtazar poprosił Cię o określenie minimalnej
liczby pomp wystarczającej do osuszenia Bajtogrodu.
Otrzymałeś mapę miasta wraz z kotliną w której jest położone. Mapa ma
kształt prostokąta, podzielonego na jednostkowych kwadratów.
Dla każdego kwadratu jednostkowego mapa określa jego wysokość nad poziomem
morza, oraz czy należy on do Bajtogrodu, czy nie. Cały teren przedstawiony
na mapie znajduje się pod wodą. Ponadto jest on otoczony dużo wyższymi
górami, które uniemożliwiają odpływ wody. Osuszenie terenów, które nie
należą do Bajtogrodu nie jest konieczne.
Każdą z pomp można umieścić na jednym z kwadratów jednostkowych
przedstawionych na mapie. Będzie ona wypompowywać wodę aż do osuszenia
kwadratu, na którym się znajduje. Osuszenie dowolnego kwadratu pociąga za
sobą obniżenie poziomu wody lub osuszenie kwadratów jednostkowych,
z których
woda jest w stanie spłynąć do kwadratu na którym ustawiono pompę. Woda może
bezpośrednio przepływać tylko między kwadratami, których rzuty na
poziomą płaszczyznę mają wspólną krawędź.
Zadanie
Napisz program, który:
-
wyczyta ze standardowego wejścia opis mapy,
-
wyznaczy minimalną liczbę pomp potrzebnych do osuszenia Bajtogrodu,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują sie dwie liczby
całkowite i , oddzielone pojedynczym odstępem, . Kolejnych wierszy zawiera opis mapy. Wiersz -wszy opisuje
-ty pas kwadratów jednostkowych na mapie. Zawiera on liczb
całkowitych , pooddzielanych
pojedynczymi odstępami, .
Liczba opisuje -ty kwadrat w -tym wierszu. Grunt w tym
kwadracie znajduje się na wysokości . Jeżeli to
kwadrat ten znajduje się na terenie Bajtogrodu, a w przeciwnym przypadku
znajduje się poza miastem.
Teren Bajtogrodu nie musi stanowić spójnej całości, może być
podzielony na kilka oddzielonych od siebie części.
Wyjście
Twój program powinien wypisać na standardowe wyjście jedną liczbę
całkowitą - minimalną liczbę pomp potrzebnych do osuszenia Bajtogrodu.
Przykład
Dla danych wejściowych:
6 9
-2 -2 -1 -1 -2 -2 -2 -12 -3
-2 1 -1 2 -8 -12 2 -12 -12
-5 3 1 1 -12 4 -6 2 -2
-5 -2 -2 2 -12 -3 4 -3 -1
-5 -6 -2 2 -12 5 6 2 -1
-4 -8 -8 -10 -12 -8 -6 -6 -4
poprawną odpowiedzią jest:
2
Na rysunku przedstawiono teren Bajtogrodu oraz przykładowe rozmieszczenie
pomp.
Autor zadania: Marcin Kubica.