网格图路径问题
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
ない
题目描述
- 给定一张 行 列的网格图,为了方便,我们约定 表示网格图第 行第 列,
- 每个格子有一个整数权值 ,注意格子的权值可以是负数,
- 给定 个人位于网格图上,第 个人的初始位置在 ,注意不保证每个人初始位置互不相同,
- 定义某人走一步为:
- 若这个人当前坐标在 ,则将该人移动至 其中之一,
- 设移动后到达 ,此时需要满足 ,
- 在任意时刻,允许任意多个人位于同一个位置。
- 定义一个人的权值为其走若干步后所有经过的格子的权值和(包括起点和终点),若一个格子被经过 次则其权值需要被累加 次。
- 特别地,若一个人没有走,则其权值为其初始位置格子的权值。
- 定义总权值为每个人走若干步数,所有人权值的最大值,而不是求和。
- 求最终所有人都走到同一个格子的最小总权值,或报告不存在最小总权值(即最小总权值为负无穷)。
输入格式
从 dis.in
读入。
- 第一行包含三个正整数 ,
- 接下来 行,第 行包含 个整数 ,
- 接下来 行,第 行包含两个正整数 ,表示第 个人的初始位置在 。
输出格式
输出到 dis.out
。
- 输出一行一个整数表示最小总权值,
- 特别地,若最小总权值不存在(即最小总权值为负无穷),输出
NO
(区分大小写)。
输入输出样例
3 3 1
1 2 3
4 5 6
7 8 9
2 2
5
3 3 2
1 2 3
4 5 6
7 8 9
2 2
3 3
15
3 3 3
1 4 -3
4 -1 4
7 8 9
1 1
2 2
3 3
10
3 3 9
1 4 -3
4 -1 4
7 8 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
11
3 3 3
-1 4 4
4 -1 4
7 8 -1
1 1
1 1
1 1
-1
3 3 3
1 4 -5
4 -1 4
7 8 9
1 1
2 2
3 3
NO
样例解释
【样例解释 1】 总权值最小的情况是第一个人不走,此时经过点只有 ,所以答案为 。
【样例解释 2】
总权值最小的情况是两个人走到 ,路线分别为 和 ,答案为 $\max(a_{2,2}+a_{2,3},a_{3,3}+a_{2,3}) = \max(11, 15) = 15$。
【样例解释 5】
总权值最小的情况是三个人都没有走,权值都为 ,答案即为 。
【样例解释 6】
容易证明最小总权值为负无穷,所以输出 NO
。
数据范围
子任务
子任务编号 | 分值 | 限制 |
---|---|---|
1 | 50 | |
2 | N/A |
- 大样例下载
- 编号为 的大样例满足编号为 的子任务的限制