Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Выверенные прыжки
После проведения сельскохозяйственных работ на одной из прямоугольных полян скопилось много стогов травы разной высоты. Поляна имеет прямоугольную форму и ее можно представить матрицей из N строк по M клеток в каждой. В клетке с координатами (x,y) находится стог травы высотой hx,y метров. 

В клетке с координатами (1,1) находится заяц, который очень хочет попасть в клетку, с координатами (N,M). Но, несмотря на силу своего желания, он не хочет тратить слишком много энергии на это действие. На прыжок из клетки с координатами (a,b) в клетку с координатами (c,d) заяц тратит ровно |ha,b – hc,d| джоулей. На весь путь заяц тратит сумму энергий, затраченных на все прыжки этого пути. 
Ввиду своей физиологии зайцы не могут прыгать произвольным образом. Точнее, любой прыжок зайца можно охарактеризовать двумя величинами: длиной и направлением. Длина прыжка – это всегда целое неотрицательное число, причём длина двух последовательных прыжков должна отличаться не более чем на единицу (резкие изменения скорости очень вредны для молодого организма зайца). Заяц, производя из клетки с координатами (x,y) прыжок длиной k, в зависимости от направления может попасть в клетки (x+k,y), (x-k,y), (x,y+k), (x,y-k) при условии, что эти клетки не находятся за пределами поляны. Менять направление прыжка можно только при условии, если длина предыдущего прыжка не превосходила 1. Первый прыжок заяц может сделать в любом направлении, но длина его должна быть равна 1. После смены направления прыжка его длина должны быть равна 1. Длина последнего прыжка также должна быть равна 1.
 

Пусть, к примеру, N=3, M=4 (см. рисунок) и первый прыжок заяц совершил из клетки c координатами (1,1) в клетку с координатами (1,2), т.е. длина этого прыжка была равна 1. Значит, длина следующего прыжка может быть равна 0, 1 или 2. При выборе длины 0, заяц останется в той же клетке и не затратит энергии. При выборе длины 1, заяц может попасть в одну из трёх соседних клеток (клетка, по четвёртому направлению, лежит за пределами поляны). Длину 2 мы можем выбрать, только сохранив направление прыжка, поэтому в этом случае мы попадём в клетку с координатами (1,4) и потратим на такой прыжок |3 -7| = 4 джоуля энергии.

Ваша задача – по заданной высоте стогов в каждой из клеток поляны, определить минимальное количество энергии, которое потребуется зайцу, чтобы попасть из клетки с координатами (1,1) в клетку с координатами (N,M).
Входные данные:
Первая строка входного файла содержит два целых числа, разделенных пробелом, N, M (1 ≤ N, M ≤ 80) – размеры поляны. В следующих N строках файла записаны по M целых чисел – высоты стогов в клетках поляны. 

Высота стога – положительное целое число, не превосходящее 106. Строки нумеруются от единицы, в порядке их вхождения во входной файл. Столбцы нумеруются слева направо.
Выходные данные:
Выходной файл должен содержать единственное число – минимальное количество энергии в джоулях, которое должен потратить заяц, чтобы попасть из клетки (1,1) в клетку (N,M). (строка единственная)

Примеры:
input.txt output.txt
1 3 4
1 3 4 7
1 2 2 2
3 1 1 1
2
2 1 5
1 1 10 1 1
0

Сложность задачи: 100%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи
Пример 1. Тест соответствует рисунку из условия. Оптимальный путь, например, может проходить по клеткам с координатами (1,1)-(2,1)-(2,2)-(3,2)-(3,3)-(3,4).

Пример 2. Оптимальный путь, например, может проходить по клеткам с координатами (1,1)-(1,2)-(1,4)-(1,5).
Показать обсуждение


На сайте гостей 17, зарегистрированных 1:
Shizao,
[Данные за последние 5 минут]