雪场缆车

Grade 100 Open Time Wednesday, 17 June 2020, 10:15 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 10:15 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 10:15 PM
Input file ski.in Output file ski.out

【题目描述】雪场缆车(ski)POJ 2375

山顶雪场可以划分为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)。