#P50756. 「POI2007」洪水 The Flood
「POI2007」洪水 The Flood
题目描述
译自 POI 2007 Stage 2. Day 1「The Flood」
你有一张 的地图,地图上所有点都被洪水淹没了。你知道地图上每个网格的海拔高度,其中一部分点属于 Byteburg 城。你需要放置尽可能少的巨型抽水机,将 Byteburg 城从洪水中解救出来。巨型抽水机会抽干该格子的所有水,直到该格子不被洪水淹没为止。
水会在有公共边的格子间从高向低流动。
输入格式
第一行两个整数 ()。
接下来 行每行 个整数 ,表示地图。第 行第 列格子的海拔高度为 ,且如果 ,则这个格子在 Byteburg 城内,否则在城外。不保证 Byteburg 城形成一个连通块。
输出格式
输出一行一个整数,表示最少需要的抽水机的数量。
样例
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