P1653 [USACO04DEC] Cow Ski Area G

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?

Line 1: Two space-separated integers: $W$ and $L$. Then input an $L×W$ matrix.

Output the minimum number of lifts needed.

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