1790: [NewOJ Contest 10] 造电梯

内存限制:512 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:135 通过:44

题目描述

现在给你一张建筑的平面图,按照要求,建筑的每一个部分都应该是轮椅使用者可以到达的,这意味着必须安装电梯。
给定的平面图是一个n*m的矩阵,里面的数字表示这个位置的高度。可以在建筑中的任意位置放置电梯,电梯可以停在所有楼层。
需要保证可以使用电梯到达所有高楼层。相同高度的楼层之间是互通的,联通准则是四联通。
需要求解最少需要多少个电梯,注意高度为1的不需要电梯。
下图展示了样例2的可视化三维图。


输入格式

输入第一行为n和m(1≤n,m≤500)。
接下来n行,每行m个整数xij,表示平面图,0≤xij≤10^9

输出格式

输出最少电梯数量

输入样例 复制

样例1:
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

输出样例 复制

样例1:
2

样例2:
2