Задача

В левом верхнем углу прямоугольной таблицы размером $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]

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main
{
	public static void main (String[] args) throws Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String[] params1 = bufferedReader.readLine().split(" ");
		int n = Integer.parseInt(params1[0]);
		int m = Integer.parseInt(params1[1]);
		int[][] A = new int[n][m];
		for (int i=0; i<n; i++)	{
	        String[] params2 = bufferedReader.readLine().split(" ");
			for (int j=0; j<m; j++)	{
				A[i][j] = Integer.parseInt(params2[j]);
			}
		}
		for (int i=1; i<n; i++)	{
			A[i][0]+=A[i-1][0];
		}
		for (int i=1; i<m; i++)	{
			A[0][i]+=A[0][i-1];
		}
		for (int i=1; i<n; i++)	{
			for (int j=1; j<m; j++) {
				A[i][j]+=Math.min(A[i-1][j],A[i][j-1]);
			}
		}
		System.out.println(A[n-1][m-1]);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

public static void main (String[] args) throws Exception

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

int n = Integer.parseInt(params1[0]);

int m = Integer.parseInt(params1[1]);

int[][] A = new int[n][m];

for (int i=0; i<n; i++) {

String[] params2 = bufferedReader.readLine().split(" ");

for (int j=0; j<m; j++) {

A[i][j] = Integer.parseInt(params2[j]);

}

for (int i=1; i<n; i++) {

A[i][0]+=A[i-1][0];

}

for (int i=1; i<m; i++) {

A[0][i]+=A[0][i-1];

}

for (int i=1; i<n; i++) {

for (int j=1; j<m; j++) {

A[i][j]+=Math.min(A[i-1][j],A[i][j-1]);

}

System.out.println(A[n-1][m-1]);

}

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

Для начала посчитаем значение для каждой клетки $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
Код решения

Facebook
X
Shares

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

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