405041 - 雪场缆车

山顶雪场可以划分为W列L行,每个方格都有一个特定的高度H(0≤H≤9 999)。游客可以从一个方格滑向相邻的并且高度不大于他所在的方格。 为了保证任意方格可以互通,雪场打算造一些直达缆车。缆车很强大,可以连接任意两个方格,而且是双向的,同一个方格可以造多台缆车。但是缆车的建造费用贵的吓人,试求打造的最少缆车数。

输入

第一行为两个整数W和L(1≤W≤500,1≤L≤500),接下来输出W×L的矩阵地图。

输出

一个整数,即最小的缆车数。

样例

输入

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

提示

把左下角作为(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)。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题