#1133. 「USACO 2014.1 Silver」Cross Country Skiing

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
ccski.in ≫ ccski.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

冬季 Moolympics 的越野滑雪赛道由一个 的高程网格描述(),每个高程在 之间。网格中的某些单元被指定为赛道的航点。Moolympics 的组织者希望为整个赛道分配一个难度等级 ,以便奶牛可以通过从一个单元滑到相邻单元(绝对高程差最多为 )的方式,从任何一个航点到达另一个航点。如果一个单元的正北、正南、正东或正西方向上有另一个单元,则这两个单元是相邻的。赛道的难度等级是 的最小值,使得所有航点都可以通过这种方式相互到达。

输入格式 ccski.in

  • 第 1 行:整数

  • 第 2 行到第 行:每一行包含 个整数高程。

  • 行到第 行:每一行包含 个值,这些值要么是 ,要么是 ,其中 表示该单元是一个航点。

输出格式 ccski.out

滑雪赛道由一个 3 x 5 的高程网格描述。左上角、右上角和右下角的单元被指定为航点。

样例

输入 #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

数据范围与提示

如果 ,三个航点可以相互到达。如果 ,则右上角的航点无法从其他两个航点到达。

题面翻译由 ChatGPT-4o 提供。