2624: 【USACO2014JAN】滑雪场评级{ Gold题3}

3. 滑雪场评级{ Gold题3}

【问题描述】

滑雪场是一个M*N(1 <= M,N <= 500)的数字矩阵表示海拔高度，每个数字表示一个范围在0 .. 1,000,000,000的高度。有些格子被指定为起点，组织者想对这些起点做难度评级。

如果起点P点是一个难度级别为D的起点，则D必须是满足以下条件的一个最小值：

（1）从一个格子只能滑到相邻的格子；

（2）这两个格子的海拔差不超过D；

（3）至少能够到达T（1 <= T <= M*N）个格子（包括起点本身）。

【文件输入】

第一行，三个用空格隔开的整数，分别表示M，N和T。

接下来2.. M+1行，每行一个N个整数，表示海拔。

接下来M+2..2M+1行，每行一个整数0或者1，其中1表示该格子是一个起点。

【文件输出】

    共一行，一个整数，所有起点的难度和。

【输入样例】

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。