АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

742. Минимальный путь в таблице

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

 
В прямоугольной таблице NxM (в каждой клетке которой записано 
некоторое число) в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку 
либо вправо, либо вниз (влево и вверх перемещаться запрещено).
При проходе через клетку с игрока берут столько у.е., какое число
записано в этой клетке (деньги берут также за первую
и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может
попасть в правый нижний угол.

Входные данные
Во входном файле задано два числа N и M - размеры таблицы (1<=N<=20,
1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов
в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

Выходные данные
В выходной файл запишите минимальную сумму, потратив которую можно попасть
в правый нижний угол.

Пример входного файла
3 4
1 1 1 1
5 2 2 100
9 4 2 1

Пример выходного файла
8


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Учебные курсы / Задачи с olympiads.ru /
741. 153 - Число способов 742. 748. 160 - Длина пути - 1 749. 161 - Длина пути - 2 750. 162 - Путь
 
время генерации 0.125 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.