P2658 汽车拉力比赛

    • 122通过
    • 521提交
  • 题目提供者NOIRP
  • 标签 二分答案 并查集 广度优先搜索,BFS 高性能
  • 难度 普及/提高-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    博艾市将要举行一场汽车拉力比赛。

    赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之间。

    其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数D,这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于D。也就是说这个难度系数D指的是保证所有路标相互可达的最小值。任一单元格和其东西南北四个方向上的单元格都是相邻的。

    输入输出格式

    输入格式:

    第一行两个整数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 40 60 80
    1 0 0 0 1
    0 0 0 0 0
    0 0 0 0 1
    输出样例#1: 复制
    21
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。