P1653 [USACO04DEC] Cow Ski Area G

# Description John’s cousin Ron lives in Colorado. He plans to teach his cows to ski, but they are very shy and do not dare to ski at tourist resorts. So he has to build his own ski area. Ron’s ski area can be divided into $W$ columns and $L$ rows ($1 \le W \le 500$, $1 \le L \le 500$). Each cell has a specific height $H$ ($0 \le H \le 9999$). Cows can ski between adjacent cells, and they are not allowed to move from a lower cell to a higher one. To ensure that any two cells can reach each other, Ron plans to build some direct lifts. Lifts are powerful: they can connect any two cells and are bidirectional. Multiple lifts can be built at the same cell. However, lifts are very expensive, so he wants to build as few as possible. What is the minimum number of lifts needed?

约翰的表哥罗恩生活在科罗拉多州。他近来打算教他的奶牛们滑雪，但是奶牛们非常害羞，不敢在游人组织的度假胜地滑雪。没办法，他只好自己建滑雪场了。罗恩的雪场可以划分为 $W$ 列 $L$ 行 $(1\le W\le 500, 1\le L\le 500)$，每个方格有一个特定的高度 $H(0\le H\le 9999)$。奶牛可以在相邻方格间滑雪，而且不能由低到高滑。 为了保证任意方格可以互通，罗恩打算造一些直达缆车。缆车很强大，可以连接任意两个方格，而且是双向的。而且同一个方格也可以造多台缆车。但是缆车的建造费用贵得吓人，所以他希望造尽量少的缆车。那最少需要造多少台呢？

第 $1$ 行：$W$，$L$。 接下来输入宽 $W$ 高 $L$ 的矩阵地图。

Output the minimum number of lifts needed.

Constraints: $1 \le W, L \le 500$, $0 \le H \le 9999$. Translated by ChatGPT 5