P3457 [POI 2007] POW-The Flood

题目描述

**译自 POI 2007 Stage 2. Day 1「[The Flood](https://szkopul.edu.pl/problemset/problem/VutzcR1iPvGuYRGZgvNksmV1/site/?key=statement)」** 你有一张 $m \times n$ 的地图,地图上所有点都被洪水淹没了。你知道地图上每个网格的海拔高度,其中一部分点属于 Byteburg 城。你需要放置尽可能少的巨型抽水机,将 Byteburg 城从洪水中解救出来。巨型抽水机会抽干该格子的所有水,直到该格子不被洪水淹没为止。 水会在有公共边的格子间从高向低流动。

输入格式

第一行两个整数 $m,n$($1 \le m,n \le 1000$)。 接下来 $m$ 行每行 $n$ 个整数 $x_{i1}, x_{i2}, \ldots, x_{in} (-1000 \le x_{ij} \lt 1000)$,表示地图。第 $i$ 行第 $j$ 列格子的海拔高度为 $\lvert x_{ij} \rvert$,且如果 $x_{ij} \gt 0$,则这个格子在 Byteburg 城内,否则在城外。不保证 Byteburg 城形成一个连通块。

输出格式

输出一行一个整数,表示最少需要的抽水机的数量。 ### 样例解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/6cal4wth.png) 翻译来自于 [LibreOJ](https://loj.ac/p/2654)。