1020 - 电梯

通过次数

4

提交次数

8

时间限制 : 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