[an error occurred while processing the directive]
Задача 02-1. Минимальный путь в таблице
Имя входного файла | input.txt |
Имя выходного файла | output.txt |
Максимальное время работы на одном тесте: | 3 секунд |
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
Формат входных данных
Во входном файле задано два числа N и M - размеры таблицы (1 <= N <= 20, 1 <= M <= 20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).
Формат выходных данных
В выходной файл запишите минимальную сумму, потратив которую можно попасть в правый нижний угол.
Пример
input.txt | output.txt |
3 4 1 1 1 1 5 2 2 100 9 4 2 1 |
8 |