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.