TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2770
  • 题目
  • P2770【USACO 2014 January Gold】难度系数
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    奶牛冬奥会的越野滑雪场可以被看做是一个M x N(1 <= M,N <= 500)的网格区域。其中每格都有一个海拔高度(海拔高度的范围:0 .. 1,000,000,000)。

    其中一些格子被设计成了滑雪的起点,赛会组织者想要给每个滑雪起点做一个难度的评级。
    一个起点P的难度系数D应该尽可能小,使得一只奶牛能够成功的滑过至少T(1 <= T <= MN)个格子。如果奶牛从P出发,它只能朝相邻的格子滑行,且要求相邻的格子的海拔高度差的绝对值不超过D。

    请帮助组织者计算出每个起点的难度系数。

    输入格式

    第一行,三个整数M, N, 和 T
    接下来是一个M x N的整数矩阵,表示每个格子的海拔高度
    接下来是一个M x N的矩阵,矩阵由数字0和1构成,数字1表示该处是一个起点。

    输出格式

    一个整数,表示所有起点的难度系数总和(可能超过int范围)

    样例输入

    3 5 10
    20 21 18 99 5
    19 22 20 16 17
    18 17 40 60 80
    1 0 0 0 0
    0 0 0 0 0
    0 0 0 0 1

    样例输出

    24

    提示

    样例说明:
    左上角处起点的难度系数为4,右下角的难度系数为20

    左上角处起点的难度系数为4->它是这么走的:

    (1,1)->(2,1)->(3,1)->(3,2)->(3,1)->(2,1)->(2,2)->(1,2)->(1,3)->(2,3)->(2,4)->(2,5)