汽车拉力比赛（并查集+二分）

阅读量：

汽车拉力比赛概述

题目描述

博艾市即将举办一场汽车拉力赛事。

比赛场地地形复杂，因此被抽象为一个 $N*M$ 的网格结构，用于表示不同区域的海拔高度 $(1 \leq M,N \leq 500)$ ，每个网格单元所对应的海拔值处于 $0$ 到 $10^9$ 的区间内。

其中部分单元格被设定为路标点。赛事组织方计划为整条赛道设定一个难度参数 $D$ ，确保参赛者从任意一个路标点前往其他路标点时，所经过路径上相邻单元格之间的海拔差异不超过 $D$ 。这里的难度系数 $D$ 指的是能够使所有路标点之间保持连通性的最小数值。任意一个单元格与其东、南、西、北四个方向上的相邻单元格均视为彼此相连。

输入格式

第 $1$ 行包含两个整数 $M$ 与 $N$ 。从第 $2$ 行至第 $M+1$ 行，每一行均包含 $N$ 个整数，用于表示对应的海拔高度。接下来，从第 $2+M$ 行至第 $1+2M$ 行，每行同样包含 $N$ 个整数，其中每个数值仅能为 $0$ 或 $1$ ，当数值为 $1$ 时，表明该单元格设置有路标。

输出格式

一个数值，具体代表赛道的难度等级 $D$ 。

样例分析与呈现

样例输入 #1

复制代码

    3 5 
    20 21 18 99 5  
    19 22 20 16 26
    18 17

全部评论 (0)

还没有任何评论哟~