11. Робот находится в левом верхнем углу прямоугольного поля. В некоторых клетках лежат золотые монеты. Робот хочет попасть в правый нижний угол, собрав как можно больше монет. Робот может двигаться: - только вправо R - только вниз D (на одну клетку за шаг) Задание: Найдите: - максимальное количество монет, которое робот может собрать - один из оптимальных путей (последовательность из букв R и D) - кратко опишите, как решали задачу (2-4 предложения) Формат входных данных: Первая строка: N M Далее N строк по M чисел: 0 или 1. Формат вывода: Две строки: - максимальное количество монет - путь Ограничения: 2 ≤ N, M ≤ 20 Пример работы: Ввод: 3 3 1 1 1 0 1 0 1 1 1 Вывод: 5 RDDR

Question

Вопрос:

11. Робот находится в левом верхнем углу прямоугольного поля. В некоторых клетках лежат золотые монеты. Робот хочет попасть в правый нижний угол, собрав как можно больше монет. Робот может двигаться: - только вправо R - только вниз D (на одну клетку за шаг) Задание: Найдите: - максимальное количество монет, которое робот может собрать - один из оптимальных путей (последовательность из букв R и D) - кратко опишите, как решали задачу (2-4 предложения) Формат входных данных: Первая строка: N M Далее N строк по M чисел: 0 или 1. Формат вывода: Две строки: - максимальное количество монет - путь Ограничения: 2 ≤ N, M ≤ 20 Пример работы: Ввод: 3 3 1 1 1 0 1 0 1 1 1 Вывод: 5 RDDR

Ответ:

ФИО:Телефон:Емаил:Полное описание сути нарушения прав (почему распространение данной информации запрещено Правообладателем):

Accepted Answer

Краткое пояснение:

Краткое пояснение: Для решения задачи используется динамическое программирование. Создается матрица, где каждая ячейка хранит максимальное количество монет, которое можно собрать, добравшись до этой клетки. Путь восстанавливается на основе этой матрицы.

Пошаговое решение:

Для решения задачи была создана матрица dp размером N x M, где dp[i][j] представляет собой максимальное количество монет, которое робот может собрать, добравшись до клетки (i, j).

1. Инициализация:

dp[0][0] = field[0][0] (количество монет в стартовой клетке).
Первая строка: dp[0][j] = dp[0][j-1] + field[0][j]. Робот может двигаться только вправо.
Первый столбец: dp[i][0] = dp[i-1][0] + field[i][0]. Робот может двигаться только вниз.

2. Заполнение матрицы:

Для остальных клеток (i > 0 и j > 0):

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + field[i][j].

Это означает, что робот приходит в клетку (i, j) либо сверху (из dp[i-1][j]), либо слева (из dp[i][j-1]), и мы выбираем путь, который дает больше монет, добавляя монеты из текущей клетки.

3. Восстановление пути:

Начиная с последней клетки (N-1, M-1), мы двигаемся назад к стартовой клетке (0, 0).

Если dp[i][j] == dp[i-1][j] + field[i][j], значит, робот пришел сверху, и предыдущий шаг был 'D' (вниз).
Если dp[i][j] == dp[i][j-1] + field[i][j], значит, робот пришел слева, и предыдущий шаг был 'R' (вправо).
Если значения равны, можно выбрать любой путь.

Путь строится в обратном порядке, поэтому в конце его нужно перевернуть.

Пример работы (3x3):

Ввод:

Матрица монет (field):

[[1, 1, 1],
 [0, 1, 0],
 [1, 1, 1]]

Матрица dp:

[[1, 2, 3],
 [1, 3, 3],
 [2, 4, 5]]

Максимальное количество монет: 5.

Восстановление пути:

(2,2) -> dp[2][2]=5. Сравниваем dp[1][2]=3 и dp[2][1]=4. 5 = 4 + field[2][2] (1). Значит, шаг был R. Текущая клетка (2,1).
(2,1) -> dp[2][1]=4. Сравниваем dp[1][1]=3 и dp[2][0]=2. 4 = 3 + field[2][1] (1). Значит, шаг был R. Текущая клетка (1,1).
(1,1) -> dp[1][1]=3. Сравниваем dp[0][1]=2 и dp[1][0]=1. 3 = 2 + field[1][1] (1). Значит, шаг был R. Текущая клетка (0,1).
(0,1) -> dp[0][1]=2. Сравниваем dp[-1][1] (нет) и dp[0][0]=1. 2 = 1 + field[0][1] (1). Значит, шаг был R. Текущая клетка (0,0).

Путь в обратном порядке: RRR. Но это не соответствует примеру. Давайте пересмотрим логику восстановления пути.

Корректное восстановление пути:

Начинаем с (N-1, M-1).
Если dp[i-1][j] > dp[i][j-1], робот пришел из (i-1, j), добавляем 'D' и переходим к (i-1, j).
Иначе (dp[i][j-1] >= dp[i-1][j]), робот пришел из (i, j-1), добавляем 'R' и переходим к (i, j-1).

Пример работы (3x3) с корректным восстановлением пути:

Матрица dp:

[[1, 2, 3],
 [1, 3, 3],
 [2, 4, 5]]

Начинаем с (2,2).

(2,2) -> dp[2][2] = 5. Сравниваем dp[1][2]=3 и dp[2][1]=4. Так как 4 > 3, мы пришли из (2,1). Добавляем 'R'. Текущая клетка (2,1).
(2,1) -> dp[2][1] = 4. Сравниваем dp[1][1]=3 и dp[2][0]=2. Так как 3 > 2, мы пришли из (1,1). Добавляем 'R'. Текущая клетка (1,1).
(1,1) -> dp[1][1] = 3. Сравниваем dp[0][1]=2 и dp[1][0]=1. Так как 2 > 1, мы пришли из (0,1). Добавляем 'R'. Текущая клетка (0,1).
(0,1) -> dp[0][1] = 2. Сравниваем dp[-1][1] (не существует) и dp[0][0]=1. Так как dp[0][0] существует и является путем, приходим из (0,0). Добавляем 'R'. Текущая клетка (0,0).

Полученный путь: RRR. Опять не совпадает с примером RDDR. Давайте пересмотрим логику для случая, когда монет поровну.

Уточненный алгоритм восстановления пути:

Начиная с (N-1, M-1), двигаемся к (0,0):

Если dp[i-1][j] > dp[i][j-1], робот пришел из (i-1, j). Предыдущий ход был 'D'. Текущая позиция (i-1, j).
Если dp[i][j-1] > dp[i-1][j], робот пришел из (i, j-1). Предыдущий ход был 'R'. Текущая позиция (i, j-1).
Если dp[i-1][j] == dp[i][j-1], нужно выбрать тот путь, который приведет к достижению (0,0). В данном случае, для получения пути 'RDDR', когда dp[1][1] = 3, мы можем прийти либо из dp[0][1] = 2 (шаг 'D'), либо из dp[1][0] = 1 (шаг 'R'). Чтобы получить 'RDDR', в случае равенства, мы должны отдавать приоритет 'R'.

Пример работы (3x3) с учетом приоритета 'R' при равенстве:

Матрица dp:

[[1, 2, 3],
 [1, 3, 3],
 [2, 4, 5]]

Начинаем с (2,2).

(2,2) -> dp[2][2]=5. Сравниваем dp[1][2]=3 и dp[2][1]=4. dp[2][1] (4) > dp[1][2] (3). Робот пришел из (2,1). Добавляем 'R'. Текущая клетка (2,1).
(2,1) -> dp[2][1]=4. Сравниваем dp[1][1]=3 и dp[2][0]=2. dp[1][1] (3) > dp[2][0] (2). Робот пришел из (1,1). Добавляем 'R'. Текущая клетка (1,1).
(1,1) -> dp[1][1]=3. Сравниваем dp[0][1]=2 и dp[1][0]=1. dp[0][1] (2) > dp[1][0] (1). Робот пришел из (0,1). Добавляем 'R'. Текущая клетка (0,1).
(0,1) -> dp[0][1]=2. Достигли первой строки. Значит, все предыдущие шаги были 'R'. Последний шаг к (0,0) будет 'D'.

Это все еще не дает RDDR. Давайте пересмотрим пример и логику.

Анализ примера:

Ввод:

Вывод:

5
RDDR

Путь RDDR означает: R (вправо), D (вниз), D (вниз), R (вправо).

Клетки, которые посещает робот:

(0,0) - монета 1
(0,1) - монета 1
(1,1) - монета 1
(2,1) - монета 1
(2,2) - монета 1

Сумма монет: 1+1+1+1+1 = 5.

Это соответствует выводу.

Теперь построим матрицу dp, исходя из этого пути:

field:

[[1, 1, 1],
 [0, 1, 0],
 [1, 1, 1]]

dp[0][0] = 1

dp[0][1] = dp[0][0] + field[0][1] = 1 + 1 = 2 (Шаг R)

dp[1][1] = dp[0][1] + field[1][1] = 2 + 1 = 3 (Шаг D)

dp[2][1] = dp[1][1] + field[2][1] = 3 + 1 = 4 (Шаг D)

dp[2][2] = dp[2][1] + field[2][2] = 4 + 1 = 5 (Шаг R)

Максимальное количество монет = 5.

Теперь, при восстановлении пути, если dp[i][j] был получен из dp[i-1][j], значит, предыдущий шаг был 'D'. Если из dp[i][j-1], значит, предыдущий шаг был 'R'.

Восстановление пути (снова, с учетом приоритета):

Матрица dp (рассчитанная по всем возможным путям):

[[1, 2, 3],
 [1, 3, 3],
 [2, 4, 5]]

Начинаем с (2,2):

(2,2). dp[2][2] = 5.
Сравниваем dp[1][2] = 3 и dp[2][1] = 4.
Так как dp[2][1] (4) (путь слева) + field[2][2] (1) = 5, робот пришел из (2,1). Предыдущий шаг был 'R'. Позиция (2,1).
(2,1). dp[2][1] = 4.
Сравниваем dp[1][1] = 3 и dp[2][0] = 2.
Так как dp[1][1] (3) (путь сверху) + field[2][1] (1) = 4, робот пришел из (1,1). Предыдущий шаг был 'D'. Позиция (1,1).
(1,1). dp[1][1] = 3.
Сравниваем dp[0][1] = 2 и dp[1][0] = 1.
Так как dp[0][1] (2) (путь сверху) + field[1][1] (1) = 3, робот пришел из (0,1). Предыдущий шаг был 'D'. Позиция (0,1).
(0,1). dp[0][1] = 2.
Сравниваем dp[-1][1] (нет) и dp[0][0] = 1.
Так как dp[0][0] (1) (путь слева) + field[0][1] (1) = 2, робот пришел из (0,0). Предыдущий шаг был 'R'. Позиция (0,0).

Путь в обратном порядке: R D D R. Переворачиваем: RDDR.

Этот алгоритм дает правильный ответ.

Вывод:

Максимальное количество монет: 5

Путь: RDDR