A2461 | $POW-The Flood$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Description 你手头有一张该市的地图。这张地图是边长为 $m\times n$ 的矩形,被划分为 $m\times n$ 个 $1\times 1$ 的小正方形。对于每个小正方形,地图上已经标注了它的海拔高度以及它是否是该市的一个组成部分。地图上的所有部分都被水淹没了。并且,由于这张地图描绘的地面周围都被高山所环绕,洪水不可能自动向外排出。显然,我们没有必要抽干那些非该市的区域。 每个巨型抽水机可以被放在任何一个 $1\times 1$ 正方形上。这些巨型抽水机将持续地抽水直到这个正方形区域里的水被彻底抽干为止。当然,由连通器原理,所有能向这个格子溢水的格子要么被抽干,要么水位被降低。每个格子能够向相邻的格子溢水,“相邻的”是指(在同一高度水平面上的射影)有公共边。

输入格式

第一行是两个数 $m,n(1\le m,n\le 1000)$. 以下 $m$ 行,每行 $n$ 个数,其绝对值表示相应格子的海拔高度;若该数为正,表示它是该市的一个区域;否则就不是。 请大家注意:所有格子的海拔高度其绝对值不超过 $1000$ ,且可以为零.

输出格式

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

输入输出样例

输入 #1

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

输出 #1

C++ 编辑器

输入

输出

A2461 | POW-The Flood

题目描述

输入格式

输出格式

输入输出样例

A2461 | $POW-The Flood$