Задание №18: Динамическое программирование (Робот в таблице)
Основные типы и прототипы задания №18:
Робот в лабиринте (Excel/Динамика)
Угловые стены и ловушки
Минимальная и максимальная сумма монет
Условие задания
Квадрат разлинован на N×N клеток (1 < N < 30). Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано целое положительное число. За один ход робот может переместиться на одну клетку влево, вверх, по диагонали влево-вверх или по диагонали вправо-вверх. Числа показывают расход энергии робота на прохождение клетки.
Определите минимальный расход энергии при переходе робота в левую верхнюю клетку поля и количество клеток с чётными числами, через которые робот проходит на пути с минимальным расходом энергии.
Пример входных данных (для таблицы размером 4×4):
При указанных входных данных минимальный расход получится при движении по маршруту 68 + 46 + 11 + 26 = 151. При этом робот проходит через 3 клетки с чётными числами (68, 46, 26). В ответе в данном случае надо записать числа 151 и 3.
Исходные данные записаны в файле 18-156.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе запишите два числа: сначала минимальный расход энергии, затем – количество пройденных клеток с чётными значениями.
Определите минимальный расход энергии при переходе робота в левую верхнюю клетку поля и количество клеток с чётными числами, через которые робот проходит на пути с минимальным расходом энергии.
Пример входных данных (для таблицы размером 4×4):
При указанных входных данных минимальный расход получится при движении по маршруту 68 + 46 + 11 + 26 = 151. При этом робот проходит через 3 клетки с чётными числами (68, 46, 26). В ответе в данном случае надо записать числа 151 и 3.Исходные данные записаны в файле 18-156.xls в виде прямоугольной таблицы, каждая ячейка которой соответствует клетке поля. В ответе запишите два числа: сначала минимальный расход энергии, затем – количество пройденных клеток с чётными значениями.
Ответ:
516 13