OI题库

【题目描述】

奶牛冬奥会的越野滑雪场地是这样设计的：它是一个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。

【提示】

在此键入。

【来源】

在此键入。