Задание 18
Условие задачи:
Робот перемещается по квадратному полю размером $N \times N$ клеток ($1 < N < 30$). Робот может выполнять две команды: "вправо" (перемещение в соседнюю правую клетку) и "вниз" (перемещение в соседнюю нижнюю клетку). Квадрат ограничен внешними стенами, через которые робот пройти не может. Между соседними клетками могут быть внутренние стены. Перед каждым запуском робота в каждой клетке лежит монета достоинством от 1 до 100. Посетив клетку, робот забирает монету с собой. Необходимо определить максимальную и минимальную денежные суммы, которые может собрать робот, пройдя из левой верхней клетки в правую нижнюю. В ответе нужно указать два числа: сначала максимальную сумму, затем минимальную. Исходные данные представлены в виде электронной таблицы.
Решение:
Эта задача является классическим примером задачи на динамическое программирование. Для ее решения нам потребуется использовать электронную таблицу с данными.
1. Максимальная сумма:
Для нахождения максимальной суммы, которую может собрать робот, мы будем заполнять таблицу, где каждая ячейка будет хранить максимальную сумму, которую можно собрать, добравшись до этой ячейки.
- Начальная ячейка (левая верхняя): Сумма в этой ячейке равна значению монеты в ней.
- Для остальных ячеек: Максимальная сумма для текущей ячейки будет равна сумме монеты в этой ячейке плюс максимальная из сумм, которые можно было собрать, добравшись до нее либо справа (из предыдущей ячейки слева), либо сверху (из предыдущей ячейки сверху). Если между ячейками есть стена, то путь через нее невозможен.
Формула для расчета максимальной суммы в ячейке $(i, j)$:
$MaxSum(i, j) = Coin(i, j) + \max(MaxSum(i-1, j) \text{ (если нет стены сверху)}, MaxSum(i, j-1) \text{ (если нет стены слева)})$
Где:
* $Coin(i, j)$ - достоинство монеты в ячейке $(i, j)$.
* $MaxSum(i-1, j)$ - максимальная сумма, собранная до ячейки выше.
* $MaxSum(i, j-1)$ - максимальная сумма, собранная до ячейки слева.
Мы заполняем эту таблицу, двигаясь от левой верхней ячейки к правой нижней. Максимальная сумма, которую может собрать робот, будет значением в правой нижней ячейке.
2. Минимальная сумма:
Аналогично нахождению максимальной суммы, мы можем найти минимальную сумму. Для этого мы будем заполнять таблицу, где каждая ячейка будет хранить минимальную сумму, которую можно собрать, добравшись до этой ячейки.
- Начальная ячейка (левая верхняя): Сумма в этой ячейке равна значению монеты в ней.
- Для остальных ячеек: Минимальная сумма для текущей ячейки будет равна сумме монеты в этой ячейке плюс минимальная из сумм, которые можно было собрать, добравшись до нее либо справа (из предыдущей ячейки слева), либо сверху (из предыдущей ячейки выше). Если между ячейками есть стена, то путь через нее невозможен.
Формула для расчета минимальной суммы в ячейке $(i, j)$:
$MinSum(i, j) = Coin(i, j) + \min(MinSum(i-1, j) \text{ (если нет стены сверху)}, MinSum(i, j-1) \text{ (если нет стены слева)})$
Где:
* $Coin(i, j)$ - достоинство монеты в ячейке $(i, j)$.
* $MinSum(i-1, j)$ - минимальная сумма, собранная до ячейки выше.
* $MinSum(i, j-1)$ - минимальная сумма, собранная до ячейки слева.
Мы заполняем эту таблицу, двигаясь от левой верхней ячейки к правой нижней. Минимальная сумма, которую может собрать робот, будет значением в правой нижней ячейке.
Для получения конкретных числовых ответов необходимо использовать предоставленный файл с электронной таблицей. В этой таблице будут указаны значения монет в каждой клетке и наличие внутренних стен.
Пример:
Если бы у нас была таблица 2x2 без стен:
| 1 | 8 |
|---|---|
| 10 | 1 |
-
Максимальная сумма:
- (1,1): 1
- (1,2): 1 + 8 = 9
- (2,1): 1 + 10 = 11
- (2,2): 1 + max(9, 11) = 1 + 11 = 12
-
Минимальная сумма:
- (1,1): 1
- (1,2): 1 + 8 = 9
- (2,1): 1 + 10 = 11
- (2,2): 1 + min(9, 11) = 1 + 9 = 10
Ответ для этого примера: 12 10
Окончательный ответ:
Для получения окончательного ответа необходимо обработать данные из электронной таблицы, используя описанные выше алгоритмы для нахождения максимальной и минимальной сумм.
