1020 - 电梯
时间限制 : 1 秒
内存限制 : 256 MB
现在给你一张建筑的平面图,按照要求,建筑的每一个部分都应该是轮椅使用者可以到达的,这意味着必须安装电梯。
给定的平面图是一个n*m的矩阵,里面的数字表示这个位置的高度。可以在建筑中的任意位置放置电梯,电梯可以停在所有楼层。
需要保证可以使用电梯到达所有高楼层。相同高度的楼层之间是互通的,联通准则是四联通。
需要求解最少需要多少个电梯,注意高度为1的不需要电梯。
下图展示了样例2的可视化三维图。
输入
输入第一行为n和m(1≤n,m≤500)。 接下来n行,每行m个整数xij,表示平面图,0≤xij≤10^9。
输出
输出最少电梯数量
样例
输入
2 3 1 2 3 1 3 2
输出
2
输入
6 7 0 0 0 0 0 0 0 0 1 2 3 2 1 0 0 1 2 3 2 1 0 0 0 0 0 0 0 0 0 1 0 5 0 0 0 0 0 0 0 0 0 0
输出
2