Прямоугольник разделен на М х N клеток. Робот может перемещаться по клеткам, сделав либо шаг вправо, либо прыжок

Содержание: Робот в прямоугольнике

Инструкция: В данной задаче у нас есть прямоугольник, разделенный на М х N клеток. Робот может перемещаться по клеткам путем совершения шага вправо или прыжка. Шаг вправо перемещает робота в соседнюю клетку справа, а прыжок переносит его на самую левую клетку, ниже текущей позиции. Однако, если робот пытается выйти за границы прямоугольника, он разрушается и задача не выполнена.

Каждая клетка прямоугольника содержит карточку с числом от -100 до 100. Одной из задач робота является сбор всех карточек при посещении каждой клетки, включая начальную и конечную клетки.

Демонстрация: Если у нас есть прямоугольник размером 3x3 и его клетки содержат числа:
-1 2 3
4 7 -6
-8 0 5

Робот может совершить последовательность перемещений: шаг вправо, прыжок, шаг вправо, шаг вправо, прыжок, шаг вправо, шаг вправо. В результате, робот посетит все клетки и соберет карточки с числами. В данном случае, сумма всех чисел на карточках будет равна: -1 + 2 + 3 + 4 + 7 + (-6) + (-8) + 0 + 5 = 6.

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

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

Тема занятия: Задача с роботом в прямоугольнике

Объяснение:

Для решения этой задачи с роботом в прямоугольнике мы можем использовать динамическое программирование. Давайте определим `dp[i][j]` как максимальную сумму чисел на карточках, которые робот может собрать, достигнув клетки (i, j).

Итак, чтобы заполнить `dp[i][j]`, у нас есть две возможности:

1. Робот пришел в клетку (i, j) из клетки (i-1, j) после сделанного прыжка вверх. В этом случае сумма на роботе будет равна `dp[i-1][j] + grid[i][j]`.
2. Робот пришел в клетку (i, j) из клетки (i, j-1) после сделанного шага вправо. В этом случае сумма на роботе будет равна `dp[i][j-1] + grid[i][j]`.

Таким образом, чтобы заполнить `dp[i][j]`, мы выбираем максимальное значение между двумя вышеприведенными вариантами.

Начиная с (0, 0) и двигаясь слева направо и сверху вниз, мы можем заполнить всю таблицу `dp`. Наконец, ответ нашей задачи будет находиться в клетке `(M-1, N-1)`, где `M` - количество строк, а `N` - количество столбцов прямоугольника.

Доп. материал:

Пусть у нас есть прямоугольник размером 3x3 с карточками чисел:

[1, 3, 1]

[1, 5, 1]

[4, 2, 1]

Максимальная сумма, которую робот может собрать, равна 12. Робот будет двигаться по клеткам в следующем порядке:

- (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2).

Совет:

Для лучшего понимания этой задачи, рекомендуется визуализировать прямоугольник, отмечая текущую позицию робота и подсчитывая максимальную сумму при каждом шаге. Это поможет лучше понять, как работает динамическое программирование в этой задаче.

Проверочное упражнение:

Решите задачу для прямоугольника размером 4x4 с карточками чисел:

[1, 2, 3, 4]

[5, -1, 6, 7]

[8, 9, -2, 10]

[11, 12, 13, 14]

Какова максимальная сумма, которую робот может собрать, и какое будет итоговое перемещение робота по клеткам?