Лыжный маршрут описывается M x N решеткой высот (1 <= M,N <= 500), каждая высота в интервале 0 .. 1,000,000,000.
Некоторые из этих ячеек помечены как стартовые точки маршрута. Организаторы хотят вычислить рейтинг трудности каждой стартовой точке. Рейтинг трудности стартовой точки P – это минимальное число D такое, что корова сможет успешно достичь как минимум T ячеек решётки (1 <= T <= MN), если она стартует в P и может двигаться в соседнюю ячейку (на север, юг, запад или восток), только если абсолютная величина разности высот в этих ячейках не превосходит D.
Вычислите рейтинг трудности для каждой стартовой точки и выведите их сумму.
INPUT FORMAT:
* Строка 1: Целые числа M, N, T.
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин равных 0 или 1, где 1 означает, что это ячейка – стартовая точка
OUTPUT FORMAT:
* Строка 1: Сумма рейтингов трудности всех стартовых точек (заметим, что это число может не поместиться в 32-битное целое, даже если каждый рейтинг в отдельности поместится).
INPUT DETAILS:
Местность описывается решеткой из 3 х 5 высот.
Верхняя левая и правая нижняя ячейки являются стартовыми точками.
Из каждой стартовой точки мы должны быть способны добраться до 10 ячеек.
OUTPUT DETAILS:
Рейтинг трудности верхнего левого угла равен 4.
Рейтинг трудности правого нижнего угла равен 20.
|
Ввод |
Вывод |
|
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 |