e-olymp 4018. Черепашка

Задача

В левом верхнем углу прямоугольной таблицы размером $n × m$ находится черепашка. На каждой клетке таблицы разлито некоторое количество кислоты. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.

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

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

В первой строке записаны два натуральных числа $n$ и $m$, не превосходящие $1000$ — размеры таблицы. Далее идёт $n$ строк, каждая из которых содержит $m$ чисел, разделённых пробелами — описание таблицы с указанием для каждой клетки содержания кислоты на ней (в миллилитрах).

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

Вывести минимальную возможную стоимость маршрута черепашки.

Тесты

Входные данные Выходные данные
[latex]3 \ 4[/latex] [latex]35[/latex]
[latex]5 \ 9 \ 4 \ 3[/latex]
[latex]3 \ 1 \ 6 \ 9[/latex]
[latex]8 \ 6 \ 8 \ 12[/latex]
[latex]1 \ 1[/latex] [latex]1[/latex]
[latex]1[/latex]
[latex]5 \ 6[/latex] [latex]25[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]1 \ 2 \ 3 \ 4 \ 5 \ 6[/latex]
[latex]4 \ 1[/latex] [latex]103[/latex]
[latex]100[/latex]
[latex]1[/latex]
[latex]1[/latex]
[latex]1[/latex]
[latex]1 \ 5[/latex] [latex]7[/latex]
[latex]1 \ 1 \ 2 \ 2 \ 1[/latex]

Код программы

Решение задачи

Для начала посчитаем значение для каждой клетки $0$-ой строки и $0$-ого столбца. Далее, для каждой клетки $\left (i, j \right )$, где $i > 0$ и $j > 0$, считаем значение клетки как сумму значения, лежащего в этой клетке и минимум из пути, откуда черепашка могла прийти (т. е. минимум из клетки $\left (i-1, j \right )$ и клетки $\left (i, j-1 \right )$). Ответом будет значение, лежащее в клетке $\left (n-1, m-1 \right ).$
Для считывания данных использовался BufferedReader, а не Scanner, так как Scanner работает дольше и из-за этого проходит не все тесты.

Ссылки

Условие задачи на e-olymp
Код решения

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *