Модуль: 11.1G Динамическое программироварие. Часть 7. Интересные задачи


5. Маршрут(2)

Дана матрица N*N, заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной K (клетку можно посещать несколько раз).

Входные данные
В первой строке находятся разделенные пробелом числа N и K. Затем идут N строк по N чисел в каждой. 2 <= N <= 100, элементы матрицы имеют значения от 1 до 9999, 1 <= K <= 2000, все числа целые.

Выходные данные
Вывести одно число - максимальную сумму.
Примеры
№Входные данныеВыходные данные
1 
5 7
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 100

7
Напишите программу
Auto
       

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++1
Комментарий учителя

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