UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3388. [Usaco2004 Dec]Cow Ski Area雪场缆车

Statistics 下载数据

Description

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

Input

  第1行:W,L.
  接下来输入宽W高L的矩阵地图.

Output

    最小的缆车数.

Sample Input

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

Sample Output

3

把左下角作为(1,1),建(3,1)H(8,2),(7,3)H(5,2),(1,3)H(2,2)三部缆车.这样任意两个方格间可以互通.

Hint

Source

Gold