За долгую и верную службу Рыцарю позволено набрать сокровищ в сокровищнице своего сеньора. Сокровищница имеет форму прямоугольника, состоящего из отдельных "клеток" — прямоугольных комнат. В каждой комнате хранятся сокровища известной стоимости. Рыцарь может вынести сколько угодно сокровищ, но пройдя через сокровищницу только один раз. Он может начать с любой комнаты вдоль внешней северной стены сокровищницы (выбор комнаты — за рыцарем). На каждом шаге он может переходить в одну из трех "южно-соседних" комнат: южную, юго-восточную или юго-западную. Из комнат, граничащих с восточной или западной внешней стеной, возможны только два направления выхода. Закончить путь Рыцарь должен в любой из комнат на южной внешней стороне сокровищницы. У Рыцаря есть план сокровищницы — прямоугольная таблица, в которой обозначены стоимости сокровищ каждой комнаты. Направлению с севера на юг соответствует направление сверху вниз на карте. По заданной карте нужно найти один из допустимых путей, обеспечивающих наибольшую возможную сумму сокровищ. Вход. Первая строка в тексте содержит два числа N и М, обозначающие "ширину" и "высоту", далее М строк по N неотрицательных целых чисел в каждой — стоимости сокровищ соответствующих комнат. Размеры сокровищницы не более чем 80x80 комнат. Выход. В первой строке указывается номер (по порядку с запада на восток) комнаты северного ряда, из которой нужно начать движение, во второй — строка символов, означающих направление очередного перехода (S — на юг, Е 6 — на юго-восток, W — на юго-запад); в третьей — полученная максимально возможная суммарная стоимость. Если есть несколько путей с максимальной суммой, вывести любой из них.
Нужно написать 3 версии кода, то есть решить задачу при помощи:
Рекурсии, ДП(динамическое программирование). мемоизации .
Код на языке С++
Препод в принцепи не требовательный, главное чтобы работало
Плачу 1-2к
Гарантия на работу | 1 год |
Средний балл | 4.96 |
Стоимость | Назначаете сами |
Эксперт | Выбираете сами |
Уникальность работы | от 70% |