In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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:
In the figure you can see the area of Byteburg and an exemplary setup of two pumps.
Task author: Marcin Kubica.