Задание 18. (И. Женецкий) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх – в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает все монеты с собой в том случае, если в клетке нечётное количество монет, иначе - половину. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. Исходные данные записаны в файле в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. Внешние и внутренние стены обозначены утолщёнными линиями. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Решение:

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

Алгоритм:

1. Создадим две матрицы такого же размера, как и входная таблица: одна для максимальных сумм (max_sum), другая для минимальных (min_sum).
2. Инициализируем левую нижнюю ячейку (начало пути) в обеих матрицах, применяя правило сбора монет к значению в этой клетке входной таблицы.
3. Заполняем первую строку и первый столбец матриц, учитывая только одно возможное направление движения (вправо для первой строки, вверх для первого столбца) и правила сбора монет.
4. Для остальных ячеек матрицы max_sum, значение вычисляется как: max(max_sum[i-1][j], max_sum[i][j-1]) + (текущая_монета_макс), где текущая_монета_макс — это значение монеты в текущей клетке, если оно нечётное, или половина, если чётное.
5. Для остальных ячеек матрицы min_sum, значение вычисляется как: min(min_sum[i-1][j], min_sum[i][j-1]) + (текущая_монета_мин), где текущая_монета_мин — это значение монеты в текущей клетке, если оно нечётное, или половина, если чётное.
6. Учитываем стены: если из клетки нельзя попасть в соседнюю (из-за стены), то соответствующее направление не рассматривается при вычислении минимума/максимума.
7. Максимальная сумма будет в правом верхнем углу матрицы max_sum, а минимальная — в правом верхнем углу матрицы min_sum.

Так как исходные данные (таблица с монетами и стенами) отсутствуют, решение будет представлено в виде алгоритма.

Ответ: Максимальная сумма, Минимальная сумма.