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

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

Черепашка

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

При проходе через клетку черепашка должна убрать все камни которые лежат в клетке. Камней в клетке столько, какое число записано в этой клетке (убирать нужно также в первой и последней клетки ее пути).

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

Входные данные:

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

Выходные данные:

В выходной файл OUTPUT.TXT выведите минимальное количество камней, которое нужно убрать, чтобы попасть в правый нижний угол.


Примеры:
input.txt output.txt
1 3 4
1 1 1 1
5 2 2 100
9 4 2 1
8
2 5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
11

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



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


Показать обсуждение


На сайте гостей 26, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]