[POI 2007] POW-The Flood

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

给定一张 $m\times n$ 的矩形地形图，所有格子都被洪水淹没，地图四周被更高的山包围，水不会自行流出。每个格子给出地面海拔以及它是否属于 Byteburg 城。

可以在任意格子放置巨型抽水机。抽水机会持续工作，直到所在格子的水被完全抽干。根据连通器原理，抽干一个格子会降低或抽干所有能够向该格子流水的格子中的水。只有具有公共边的格子相邻，水只能向下流动。

不要求抽干城外格子。求至少需要多少台抽水机，才能抽干所有城市格子。

输入格式

第一行两个整数 $m,n$。

接下来 $m$ 行，每行 $n$ 个整数 $x_{ij}$。格子 $(i,j)$ 的海拔为 $|x_{ij}|$；若 $x_{ij}>0$，该格子属于城市，否则属于城外。

输出格式

输出一个整数，表示最少需要的抽水机数量。

样例输入 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

2

数据范围

• $1\le m,n\le1000$；
• $-1000\le x_{ij}<1000$；
• 格子的海拔为 $|x_{ij}|$，所以输入 $0$ 表示海拔为 $0$ 的城外格子；
• 城市可以不连通，也可能没有城市格子。