题目描述

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 $m\times n$ rectangle, divided into unitary squares. For each such square the map tells its height above sea level and alsowhether it is a part of Byteburg or not. The whole area depicted in the map is under water. Furthermore, it issurrounded by much higher mountains, making the outflow of water impossible. Obviously, there is no needto 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 thewater 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.

Task

Write a programme that:

• reads description of the map from the standard input,

• determines the minimum number of pumps needed to drain whole Byteburg,

• writes out the outcome to the standard output.

给定一张地势图，所有的点都被水淹没，现在有一些关键点，要求放最少的水泵使所有关键点的水都被抽干

输入格式

In the first line of the standard input there are two integers $m$ and $n$, separated by a single space, $1 \le n, m \le 1\ 000$. The following $m$ lines contain the description of the map. The $(i+1)$'th line describes the $i$'th row of unitary squares in the map. It contains $n$ integers $x_{i,1}, x_{i,2}, ..., x_{i_n}$, separated by single spaces,$-1\ 000 \le x_{i,j} \le 1\ 000$ ,$x_{i,j} \ne 1000$ . The number $x_{i,j}$ describes the $j$'th square of the $i$'th line. The ground level in this square is $|x_{i,j}|$ above sea level. If $x_{i,j} > 0$, 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 pumpsneeded to drain Byteburg.

题目大意

Description 你手头有一张该市的地图。这张地图是边长为 m∗n 的矩形,被划分为m∗n个1∗1的小正方形。对于每个小正方形,地图上已经标注了它的海拔高度以及它是否是该市的一个组成部分。地图上的所有部分都被水淹没了。并且,由于这张地图描绘的地面周围都被高山所环绕,洪水不可能自动向外排出。显然,我们没有必要抽干那些非该市的区域。

每个巨型抽水机可以被放在任何一个1∗1正方形上。这些巨型抽水机将持续地抽水直到这个正方形区域里的水被彻底抽干为止。当然,由连通器原理,所有能向这个格子溢水的格子要么被抽干,要么水位被降低。每个格子能够向相邻的格子溢水,“相邻的”是指(在同一高度水平面上的射影)有公共边。

Input

第一行是两个数m,n(1<=m,n<=1000).

以下 m 行,每行 n 个数,其绝对值表示相应格子的海拔高度;若该数为正,表示它是该市的一个区域;否则就不是。

请大家注意:所有格子的海拔高度其绝对值不超过 1000 ,且可以为零.

Output

只有一行,包含一个整数,表示至少需要放置的巨型抽水机数目。

感谢@FlashHu 提供的翻译

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

2