Вывести маршрут максимальной стоимости
В левом верхнем углу прямоугольной таблицы размером
N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.
Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.
Формат ввода
В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.
Формат вывода
Первая строка выходных данных содержит максимальную возможную сумму, вторая — маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
import java.util.Scanner;
import java.util.Random;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Введите размеры таблицы N и M через пробел:");
int N = scanner.nextInt();
int M = scanner.nextInt();
int[][] table = generateRandomMatrix(N, M);
System.out.println("Сгенерированная матрица:");
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
System.out.print(table[i][j] + " ");
}
System.out.println();
}
String[] result = findMaxSumRoute(N, M, table);
System.out.println("Максимальная сумма: " + result[0]);
System.out.println("Маршрут: " + result[1]);
}
public static int[][] generateRandomMatrix(int N, int M) {
int[][] matrix = new int[N][M];
Random random = new Random();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
matrix[i][j] = random.nextInt(101);
}
}
return matrix;
}
public static String[] findMaxSumRoute(int N, int M, int[][] table) {
int[][] maxSum = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (i == 0 && j == 0) {
maxSum[i][j] = table[i][j];
} else if (i == 0) {
maxSum[i][j] = maxSum[i][j - 1] + table[i][j];
} else if (j == 0) {
maxSum[i][j] = maxSum[i - 1][j] + table[i][j];
} else {
maxSum[i][j] = Math.max(maxSum[i - 1][j], maxSum[i][j - 1]) + table[i][j];
}
}
}
StringBuilder route = new StringBuilder();
int i = N - 1, j = M - 1;
while (i > 0 || j > 0) {
if (i == 0) {
route.append("R");
j--;
} else if (j == 0) {
route.append("D");
i--;
} else if (maxSum[i - 1][j] > maxSum[i][j - 1]) {
route.append("D");
i--;
} else {
route.append("R");
j--;
}
}
String reversedRoute = route.reverse().toString();
return new String[]{Integer.toString(maxSum[N - 1][M - 1]), reversedRoute};
}
}