/ Vijos / 题库 /

旱冰场

旱冰场

时间限制:1秒  内存限制:256M


【题目描述】

  小H的旱冰场可以划分为 \(N\) 列 \(M\) 行,每个方格有一个特定的高度 \(H\)。溜冰爱好者可以在相邻方格间滑冰,而且不能由低滑到高滑(高度相同,则可以相互滑到)。为了保证任意方格可以互通,小H打算造一些电动滑轨,电动滑轨功能强大,可以连接任意两个方格,而且是双向可达的。同一个方格也可以造多台电动滑轨。请问,小H最少需要造多少电动滑轨才能保证任意方格可以互通?

【输入格式】

  第一行为 \(N\) 和 \(M\) 两个整数。接下来输入 \(N\) 列 \(M\) 行的整数矩阵,表示旱冰场每个格子的高度。

【输出格式】

  输出最小需要的电动滑轨数。

【输入输出样例1】

 Input

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

 Output

3

【测试点性质】

  对于全部的测试点,保证 \(1\le N,M\le 500\),\(0\le H\le 9999\)。

【来源】

  Mr.he

信息

ID
3239
难度
10
分类
图结构 | 强连通分量拓扑排序 点击显示
标签
递交数
2
已通过
0
通过率
0%
被复制
1
上传者