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.
Byteburg, the capital of Byteotia, is a picturesque city situated in a valley in the midst of mountains. Unfortunately, recent heavy rainfall has caused a flood - all the Byteburg is now completely under water. Byteasar, the king of Byteotia, has summoned his most enlightened advisors, including you, to a council. After long deliberations the council agreed to bring a few pumps, set them up in the flooded area and drain Byteburg. The king has asked you to determine the minimum number of pumps sufficing to drain the city.
You are provided with a map of the city and the valley it is situated in. The map is in the shape of a rectangle, divided into unitary squares. For each such square the map tells its height above sea level and also whether it is a part of Byteburg or not. The whole area depicted in the map is under water. Furthermore, it is surrounded by much higher mountains, making the outflow of water impossible. Obviously, there is no need to drain the area that does not belong to Byteburg.
Each pump can be placed in any unitary square depicted in the map. The pump will be drawing the water until its square is completely drained. Of course, the communicating tubes principle makes its work, so draining one square results in lowering the water level or complete draining of those squares from which the water can flow down to the one with the pump. Water can flow only between squares with a common side (or, more exact, squares whose projections onto horizontal plane have a common side, since the squares may be at different level). Apart from that, the water obviously only flows down.
Write a programme that:
In the first line of the standard input there are two integers and , separated by a single space, . The following lines contain the description of the map. The 'th line describes the 'th row of unitary squares in the map. It contains integers , separated by single spaces, , . The number describes the 'th square of the 'th line. The ground level in this square is above sea level. If , then the square is part of Byteburg, otherwise it is outside the city. Notice, that the area of Byteburg need not be connected. In fact the city may have several separate parts.
Your programme should write out one integer to the standard output - the minimum number of pumps needed to drain Byteburg.
For the input data:
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
the correct result is:
2
In the figure you can see the area of Byteburg and an exemplary setup of two pumps.
Task author: Marcin Kubica.