[USACO JAN14]滑雪场地的难度系数

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file skilevel.in Output file skilevel.out

【题目描述】


奶牛冬奥会的越野滑雪场地是这样设计的:它是一个M*N(1 <= M,N <=500)的网格,每个格子标记着它的海拔高度数据,每个数据都在0..1,000,000,000的范围内。在这些网格中,有些格子被设定为场地中的起点位置。冬奥会的组织方希望为每个起点设置一个难度系数值,起点P的难度值为一个可能的最小值D,其中D值要保证能使一头奶牛能成功地从P出发,到达至少T个单元格(1 <= T <= MN),如果它从P出发,它只能从该单元格移动到跟它相邻的且两个单元格高度差不超过D的单元格。两个单元格相邻是指一个单元格在另一个单元格的东、西、南、或北方向上。

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


【输入格式】


输入格式:

第1行:整数M,N,T;

第2~M+1行:每行有N个整数,为高度值;

第M+2~2M+1行:每行有N个数,每个数为0或1,1表示该单元格为一个起点。


【输出格式】


输出只有一个数,表示所有起点难度系数值的总和。注意结果可能会超过32位二进制所能表示的整数。


【样例输入】

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。

【提示】

在此键入。

【来源】

在此键入。