题目描述

农夫约翰的表弟，农夫罗恩，住在科罗拉多州的山区，最近他教会了他的奶牛滑雪。不幸的是，他的奶牛有点胆小，害怕在当地滑雪场的人群中滑雪，所以罗恩决定在他的农场后面建造自己的私人滑雪区。

罗恩的滑雪区是一个宽为 (W) 、长为 (L) 的矩形“土地方格”区域（(1 ≤ W ≤ 500)；(1 ≤ L ≤ 500)）。每个土地方格的海拔高度 (H) 是一个整数（(0 ≤ H ≤ 9999)）。奶牛可以在任意两个相邻的土地方格之间水平或垂直滑行，但绝不能斜着滑行。奶牛可以从较高的方格滑向较低的方格，反之则不行，并且它们可以在两个相邻且高度相同的方格之间双向滑行。

罗恩想建造他的滑雪区，以便他的奶牛可以通过滑雪（如上述方式）和乘坐滑雪缆车的组合在任意两个方格之间通行。滑雪缆车可以在滑雪区的任意两个方格之间建造，无论高度如何。滑雪缆车是双向的。滑雪缆车可以相互交叉，因为它们可以建在离地面不同的高度，并且多个滑雪缆车可以在同一个方格开始或结束。由于建造滑雪缆车很昂贵，罗恩希望尽量减少他必须建造的滑雪缆车数量，以使他的奶牛能够在他的滑雪区的所有方格之间通行。

找到所需的最少滑雪缆车数量，以确保奶牛可以通过滑雪和乘坐缆车的组合从任意一个方格到达任意另一个方格。

输入

第 1 行：两个用空格分隔的整数：(W) 和 (L)

第 2 行到 (L + 1) 行：(L) 行，每行有 (W) 个用空格分隔的整数，对应每个土地方格的高度。

输出

第 1 行：一个整数，等于罗恩需要建造的最少滑雪缆车数量，以确保他的奶牛可以通过滑雪和乘坐缆车的组合从任意一个方格到达任意另一个方格。

9 3
1 1 1 2 2 2 1 1 1
1 2 1 2 3 2 1 2 1
1 1 1 2 2 2 1 1 1

3

提示

这个问题的输入数据量很大，请使用 scanf() 而不是 cin 来读取数据，以避免超时。

输出细节

罗恩建造了三部缆车。以（1，1）作为左下角的方格，

这三部缆车分别连接（3，1）和（8，2），（7，3）和（5，2），以及（1，3）和（2，2）。现在所有的位置都连通了。例如，一头奶牛想要从（9，1）前往（2，2），它会先滑行：（9，1）→（8，1）→（7，1）→（7，2）→（7，3），然后乘坐从（7，3）到（5，2）的缆车，接着滑行：（5，2）→（4，2）→（3，2）→（3，3）→（2，3）→（1，3），最后乘坐从（1，3）到（2，2）的缆车。不存在使用少于三部缆车的解决方案。

来源

USACO 2004 年 12 月金牌赛