Квадрат разлинован на N х N клеток. В каждой клетке стоит натуральное число. Исполнитель Робот может перемещаться по клеткам, выполняя
одну из трёх операций:
1. Переход на одну клетку вправо.
2. Переход на одну клетку вверх.
3. Переход вправо вверх на одну клетку по диагонали.
В случае хода типа 1 или 2 за ход сумма набранных Роботом
увеличивается на число, стоящее в клетке, на которую перемещается Робот.
В случае хода типа 3 сумма набранных Роботом увеличивается
на удвоенное число, стоящее в клетке, на которую перемещается Робот.
В начале Робот стоит в левой нижней клетке и ему присвоено число
, указанное в этой клетке.
Выходить за пределы квадрата Роботу запрещено.
Определите максимальное и минимальное количество , которое
может набрать Робот, пройдя из левой нижней клетки в правую верхнюю.
В ответе укажите два числа — сначала максимальное количество, затем
минимальное.
Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.
В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пусть `grid` - это таблица размером N х N, которая содержит числа, расположенные в каждой клетке квадрата. Построим две таблицы: `max_sum` и `min_sum`, размером N х N.
Шаги решения задачи:
1. Заполняем таблицы `max_sum` и `min_sum` значениями для начальной позиции Робота (левая нижняя клетка). В первой ячейке `max_sum[0][0]` и `min_sum[0][0]` будет содержаться значение `grid[0][0]`.
2. Заполняем первую строку таблицы `max_sum` и `min_sum` значениями, которые Робот может достигнуть, перемещаясь только вправо. Робот может попасть только в ячейки (0, 1), (0, 2), ..., (0, N-1), поэтому для каждой ячейки `max_sum[0][j]` и `min_sum[0][j]` мы прибавляем значение `grid[0][j]` из предыдущей ячейки `max_sum[0][j-1]` и:`min_sum[0][j-1]`.
3. Аналогично заполняем первый столбик таблицы `max_sum` и `min_sum` значениями, которые Робот может достигнуть, перемещаясь только вверх. Робот может попасть только в ячейки (1, 0), (2, 0), ..., (N-1, 0), поэтому для каждой ячейки `max_sum[i][0]` и `min_sum[i][0]` мы прибавляем значение `grid[i][0]` из предыдущей ячейки `max_sum[i-1][0]` и `min_sum[i-1][0]`.
4. Теперь мы можем заполнить оставшиеся ячейки таблиц `max_sum` и `min_sum` с использованием трёх операций Робота. Робот может прийти в ячейку (i, j) из ячейки (i-1, j), (i, j-1) или (i-1, j-1). Мы выбираем путь, который дает максимальную и минимальную сумму.
- Для ячейки (i, j) мы находим максимум из трех возможностей:
- `max_sum[i-1][j] + grid[i][j]`: Робот пришел снизу.
- `max_sum[i][j-1] + grid[i][j]`: Робот пришел слева.
- `max_sum[i-1][j-1] + 2 * grid[i][j]`: Робот пришел по диагонали.
- То же самое делаем для таблицы `min_sum`, только заменяем максимум на минимум в формуле.
5. В конце мы получаем значения `max_sum[N-1][N-1]` и `min_sum[N-1][N-1]`, которые представляют максимальную и минимальную сумму, которую Робот может набрать, пройдя из левой нижней клетки в правую верхнюю.
Вот код на языке Python, который реализует решение:
```python
def max_min_robot_sum(grid):
N = len(grid)
max_sum = [[0] * N for _ in range(N)]
min_sum = [[0] * N for _ in range(N)]
# Шаг 1: Заполняем начальную позицию
max_sum[0][0] = grid[0][0]
min_sum[0][0] = grid[0][0]
# Шаг 2: Заполняем первую строку
for j in range(1, N):
max_sum[0][j] = max_sum[0][j-1] + grid[0][j]
min_sum[0][j] = min_sum[0][j-1] + grid[0][j]
# Шаг 3: Заполняем первый столбец
for i in range(1, N):
max_sum[i][0] = max_sum[i-1][0] + grid[i][0]
min_sum[i][0] = min_sum[i-1][0] + grid[i][0]
# Шаг 4: Расчет оставшихся ячеек
for i in range(1, N):
for j in range(1, N):
max_sum[i][j] = max(max_sum[i-1][j], max_sum[i][j-1], max_sum[i-1][j-1] + 2 * grid[i][j])
min_sum[i][j] = min(min_sum[i-1][j], min_sum[i][j-1], min_sum[i-1][j-1] + 2 * grid[i][j])
# Шаг 5: Возвращаем результат
return max_sum[N-1][N-1], min_sum[N-1][N-1]
# Пример использования
grid = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
max_sum, min_sum = max_min_robot_sum(grid)
print("Максимальная сумма:", max_sum)
print("Минимальная сумма:", min_sum)
```
Этот код будет работать для примера `grid`, содержащего числа от 1 до 9.
Важно отметить, что данный код решает задачу для квадратного квадрата размером N х N.